一列1-n的数，其中有一个重复的（意味着有一个数missing），找出重复了一次的数以及缺少的那个数
思路一：开个dict存每个数出现几次，再扫一遍找出duplicate和missing
1 #645
2 #Runtime: 447 ms
3 #Memory Usage: 15.5 MB
4
5 class Solution(object):
6 def findErrorNums(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: List[int]
10 """
11 dict_num = {}
12 ans = [0, 0]
13 for i in nums:
14 if i not in dict_num:
15 dict_num[i] = 1
16 else:
17 dict_num[i] += 1
18 for i in range(1, len(nums) + 1):
19 if i not in dict_num:
20 ans[1] = i
21 elif dict_num[i] > 1:
22 ans[0] = i
23 return ans
思路二（看solution得到的启发，不使用其他dict等多余存储）：第一遍扫的时候将位于nums[abs(nums[i]) - 1]的数*-1，发现某个数已经是负的话说明duplicate，第二遍再扫一次，找出仍然大于0的数，其对应的下标就是missing的那个
1 #645
2 #Runtime: 495 ms
3 #Memory Usage: 14.2 MB
4
5 class Solution(object):
6 def findErrorNums(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: List[int]
10 """
11 ans = [0, 0]
12 for i in range(len(nums)):
13 if nums[abs(nums[i]) - 1] < 0:
14 ans[0] = abs(nums[i])
15 else:
16 nums[abs(nums[i]) - 1] *= -1
17 for i in range(len(nums)):
18 if nums[i] > 0:
19 ans[1] = i + 1
20 return ans
思路三（看solution得到的启发，异或思想，只用一重for循环，但需要一个dict）：原理：a^b^b=a
1 #645
2 #Runtime: 471 ms
3 #Memory Usage: 15.7 MB
4
5 class Solution(object):
6 def findErrorNums(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: List[int]
10 """
11 dict_num = {}
12 ans = [0, 0]
13 for i in range(len(nums)):
14 if nums[i] not in dict_num:
15 dict_num[nums[i]] = 1
16 else:
17 ans[0] = nums[i]
18 dict_num[nums[i]] += 1
19 ans[1] ^= (i + 1)
20 ans[1] ^= nums[i]
21 ans[1] ^= ans[0]
22 return ans
思路四（看solution得到的启发，异或思想，但实际只需要三重for循环，不需要额外dict），原理：a^b^b=a，找出a和b二进制最后一位出现不同的位置，将1-n分为两类，扫一遍nums和1-n之后，在其中一类会出现a，另一类出现b^b^b（=b），再扫一次nums就能找到b位于哪一类
1 #645
2 #Runtime: 306 ms
3 #Memory Usage: 14.8 MB
4
5 class Solution(object):
6 def findErrorNums(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: List[int]
10 """
11 ans = [0, 0]
12 xor = 0
13 for i in range(len(nums)):
14 xor ^= (i + 1)
15 xor ^= nums[i]
16 rightmostbit = xor & ~(xor - 1)
17 for i in range(len(nums)):
18 if (i + 1) & rightmostbit != 0:
19 ans[1] ^= (i + 1)
20 else:
21 ans[0] ^= (i + 1)
22 if nums[i] & rightmostbit != 0:
23 ans[1] ^= nums[i]
24 else:
25 ans[0] ^= nums[i]
26 for i in nums:
27 if ans[0] == i:
28 return ans
29 return [ans[1], ans[0]]