一列1-n的數(shù)，其中有一個(gè)重復(fù)的（意味著有一個(gè)數(shù)missing），找出重復(fù)了一次的數(shù)以及缺少的那個(gè)數(shù)
思路一：開(kāi)個(gè)dict存每個(gè)數(shù)出現(xiàn)幾次，再掃一遍找出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得到的啟發(fā)，不使用其他dict等多余存儲(chǔ)）：第一遍掃的時(shí)候?qū)⑽挥趎ums[abs(nums[i]) - 1]的數(shù)*-1，發(fā)現(xiàn)某個(gè)數(shù)已經(jīng)是負(fù)的話說(shuō)明duplicate，第二遍再掃一次，找出仍然大于0的數(shù)，其對(duì)應(yīng)的下標(biāo)就是missing的那個(gè)
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得到的啟發(fā)，異或思想，只用一重for循環(huán)，但需要一個(gè)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得到的啟發(fā)，異或思想，但實(shí)際只需要三重for循環(huán)，不需要額外dict），原理：a^b^b=a，找出a和b二進(jìn)制最后一位出現(xiàn)不同的位置，將1-n分為兩類，掃一遍nums和1-n之后，在其中一類會(huì)出現(xiàn)a，另一類出現(xiàn)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]]