一列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]]