题目分析

这个题目和昨天讲解的题目非常类似，有的小伙伴就会说骗人，根本不一样，那下面让我们来康一康吧。

位运算

题目中说集合S中的元素包含从1到n的整数，而且其中的某一个元素替换成了另一个。这其实就是相当于所有数字都出现两次，除了一个出现一次，一个出现三次。因为我们已知数据从1到n，我们可以额外添加一组从1到n的数据，假设x替换成了y，那么新数组为x出现1次，y出现3次，其他的数据都出现2次。是不是和昨天讲解的题目非常相似。只是昨天的数据已经给出了出现两次，今天的数据需要从1到n额外添加一次。

from functools import reduce


class Solution(object):
    def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        a = reduce(lambda x, y: x ^ y, nums + list(range(1, n + 1)))
        b = 1
        part1 = 0
        part2 = 0
        while not (a & b):
            b <<= 1
        for x in nums:
            if x & b:
                part1 ^= x
            else:
                part2 ^= x
        for x in range(1, n + 1):
            if x & b:
                part1 ^= x
            else:
                part2 ^= x
        for x in nums:
            if part1 == x:
                return [part1, part2]
        return [part2, part1]

刷题总结

这几天的强化位运算找数字问题，让小伙伴们明白，遇到相同数字的问题，首先需要考虑异或的方法，往往可以节省大量的内存空间。