# 题意：错误的集合问题。集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。给定一个数组 nums 代表了集合 S 发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
# 这道题没有限制时空复杂度，故可以用多种方法做，我用了位运算的方法解决，时间复杂度O(n)空间O(1)理论上较优
# 解法：因为题目说包含1-n的整数，故本应该是range(1,n+1),现在里面缺失了一位并多了一位重复，让我们找出这两个
# 1. 若要用O(1)空间复杂度则不考虑辅助数据结构比如哈希字典。联想到数列中找到不重复的数字，可以用异或的性质：任何数异或自己为0（异或是不同为1，相同为0），将原list和现list相加，只有重复和缺失值没有重复。若全部异或，则剩下的就是重复xor缺失
# 2. 接下来我们需要将重复和缺失给分开来，我们保留上一步的结果res。又有若：a xor b = c，那么c中为1的位一定只出现在a或只出现在b，如果我们找出res中第一个1的位置，令新变量为该位置的one-hot，那么新变量与重复或缺失相与的结果一定一个不为0（因为该变量只有该处为1），一个为0
# 3. 因为可以分成两组，那么两组分别与0(a,b)与得出的两个结果就分别是重复和缺失了。所以将0与现在s所有数相异或，并用if相与筛选分为两波。不用关心其他数字因为其他数都有重复无论如何都会异或=0.
# 4. 最后a和b就是重复和缺失，然后判别哪个是就需要再遍历一次s若a再s则a为重复剩下为缺失。返回即可。
# 其他解法（以后补充）：字典，暴力，排序，etc.。


class Solution:
    def findErrorNums(self, nums):
        # inputs: nums: List[int]
        # outputs: List[int]
        # 用位运算来解
        res,a,b,x = 0,0,0,1
        # 异或本应该的s
        for i in range(1,len(nums)+1):
            res ^= i
        # 再异或现在的s，结果为重复数xor缺失数
        for item in nums:
            res ^= item
        # 找出res自左向右第一个为1的位置，最后的x类似00100
        while x&res==0: x <<= 1  # 这里要写==0，因为可能会出现其他值，不能写!=1
        # 用x来区分缺失和重复
        for item in nums:
            if item & x:
                a ^= item
            else:
                b ^= item
        for i in range(1,len(nums)+1):
            if i & x:
                a ^= i
            else:
                b ^= i
        for num in nums:
            if num == a:
                return [a,b]
            if num == b:
                return [b,a]
        return []
        
        
# 题意：错误的集合问题。集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。给定一个数组 nums 代表了集合 S 发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
# 这道题没有限制时空复杂度，故可以用多种方法做，我用了位运算的方法解决，时间复杂度O(n)空间O(1)理论上较优
# 解法：因为题目说包含1-n的整数，故本应该是range(1,n+1),现在里面缺失了一位并多了一位重复，让我们找出这两个
# 1. 若要用O(1)空间复杂度则不考虑辅助数据结构比如哈希字典。联想到数列中找到不重复的数字，可以用异或的性质：任何数异或自己为0（异或是不同为1，相同为0），将原list和现list相加，只有重复和缺失值没有重复。若全部异或，则剩下的就是重复xor缺失
# 2. 接下来我们需要将重复和缺失给分开来，我们保留上一步的结果res。又有若：a xor b = c，那么c中为1的位一定只出现在a或只出现在b，如果我们找出res中第一个1的位置，令新变量为该位置的one-hot，那么新变量与重复或缺失相与的结果一定一个不为0（因为该变量只有该处为1），一个为0
# 3. 因为可以分成两组，那么两组分别与0(a,b)与得出的两个结果就分别是重复和缺失了。所以将0与现在s所有数相异或，并用if相与筛选分为两波。不用关心其他数字因为其他数都有重复无论如何都会异或=0.
# 4. 最后a和b就是重复和缺失，然后判别哪个是就需要再遍历一次s若a再s则a为重复剩下为缺失。返回即可。
# 其他解法（以后补充）：字典，暴力，排序，etc.。


class Solution:
    def findErrorNums(self, nums):
        # inputs: nums: List[int]
        # outputs: List[int]
        # 用位运算来解
        res,a,b,x = 0,0,0,1
        # 异或本应该的s
        for i in range(1,len(nums)+1):
            res ^= i
        # 再异或现在的s，结果为重复数xor缺失数
        for item in nums:
            res ^= item
        # 找出res自左向右第一个为1的位置，最后的x类似00100
        while x&res==0: x <<= 1  # 这里要写==0，因为可能会出现其他值，不能写!=1
        # 用x来区分缺失和重复
        for item in nums:
            if item & x:
                a ^= item
            else:
                b ^= item
        for i in range(1,len(nums)+1):
            if i & x:
                a ^= i
            else:
                b ^= i
        for num in nums:
            if num == a:
                return [a,b]
            if num == b:
                return [b,a]
        return []
        
        
# 题意：错误的集合问题。集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。给定一个数组 nums 代表了集合 S 发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。 # 这道题没有限制时空复杂度，故可以用多种方法做，我用了位运算的方法解决，时间复杂度O(n)空间O(1)理论上较优 # 解法：因为题目说包含1-n的整数，故本应该是range(1,n+1),现在里面缺失了一位并多了一位重复，让我们找出这两个 # 1. 若要用O(1)空间复杂度则不考虑辅助数据结构比如哈希字典。联想到数列中找到不重复的数字，可以用异或的性质：任何数异或自己为0（异或是不同为1，相同为0），将原list和现list相加，只有重复和缺失值没有重复。若全部异或，则剩下的就是重复xor缺失 # 2. 接下来我们需要将重复和缺失给分开来，我们保留上一步的结果res。又有若：a xor b = c，那么c中为1的位一定只出现在a或只出现在b，如果我们找出res中第一个1的位置，令新变量为该位置的one-hot，那么新变量与重复或缺失相与的结果一定一个不为0（因为该变量只有该处为1），一个为0 # 3. 因为可以分成两组，那么两组分别与0(a,b)与得出的两个结果就分别是重复和缺失了。所以将0与现在s所有数相异或，并用if相与筛选分为两波。不用关心其他数字因为其他数都有重复无论如何都会异或=0. # 4. 最后a和b就是重复和缺失，然后判别哪个是就需要再遍历一次s若a再s则a为重复剩下为缺失。返回即可。 # 其他解法（以后补充）：字典，暴力，排序，etc.。 # inputs: nums: List[int] # outputs: List[int] # 用位运算来解 # 异或本应该的s # 再异或现在的s，结果为重复数xor缺失数 # 找出res自左向右第一个为1的位置，最后的x类似00100 # 这里要写==0，因为可能会出现其他值，不能写!=1 # 用x来区分缺失和重复