在一維數(shù)組中的考察中，最常見的就是找出數(shù)組中的重復(fù)數(shù)、只出現(xiàn)一次的數(shù)或者丟失（消失）數(shù)等等。

一般來說，首先想到的就是用哈希表（集合）來記錄出現(xiàn)過的數(shù)，基本所有的題都可以用集合來做，而技巧性在于有時(shí)可以把原數(shù)組自身作為哈希表；
其次就是位運(yùn)算，原理是相同的數(shù)做異或運(yùn)算 ^ 會(huì)得到0，而一個(gè)數(shù)與0做異或會(huì)得到這個(gè)數(shù)本身；
最后，在排好序或者對空間要求為O(1)但又不能修改原數(shù)組的情況下，二分查找也是一種方法。

136. 只出現(xiàn)一次的數(shù)字（找出一個(gè)只出現(xiàn)一次的數(shù)字）

class Solution:def singleNumber(self, nums: List[int]) -> int:ans = set()for num in nums:if num in ans:ans.remove(num)else:ans.add(num)return ans.pop()

雖然可以用集合解決，但是此題最優(yōu)的做法是位運(yùn)算，數(shù)組里面所有相同的數(shù)異或會(huì)得到0，而那個(gè)只出現(xiàn)一次的數(shù)再與0做異或，直接得到結(jié)果本身，代碼如下：

class Solution:def singleNumber(self, nums: List[int]) -> int:ans = nums[0]for i in range(1, len(nums)):ans = ans ^ nums[i]return ans

217. 存在重復(fù)元素（是否存在重復(fù)元素）

class Solution:def containsDuplicate(self, nums: List[int]) -> bool:temp = set()for num in nums:if num in temp:return Trueelse:temp.add(num)return False

劍指 Offer 03. 數(shù)組中重復(fù)的數(shù)字（找出一個(gè)重復(fù)元素）

class Solution:def findRepeatNumber(self, nums: List[int]) -> int:temp = set()for num in nums:if num in temp:return numelse:temp.add(num)return -1

用集合輕松解決，但是可以不使用額外的集合，而是將原數(shù)組本身當(dāng)作集合，通過交換使得數(shù)組的值與索引（下標(biāo)）一一對應(yīng)，若出現(xiàn)兩個(gè)值對應(yīng)同一個(gè)索引，即為重復(fù)的元素。

class Solution:def findRepeatNumber(self, nums: [int]) -> int:i = 0while i < len(nums):if nums[i] == i: # 值與索引已經(jīng)相同，跳過i += 1continueif nums[i] == nums[nums[i]]: # 值與值所指向下標(biāo)的值一樣，說明是重復(fù)數(shù)return nums[i]nums[nums[i]], nums[i] = nums[i], nums[nums[i]]return -1

注意： Python 中， a, b = c, d操作的原理是先暫存元組 (c,d) ，然后 “按左右順序” 賦值給 a 和 b 。因此，若寫為 nums[i], nums[nums[i]] = nums[nums[i]], nums[i]，則 nums[i] 會(huì)先被賦值，之后 nums[nums[i]] 指向的元素則會(huì)出錯(cuò)。

260. 只出現(xiàn)一次的數(shù)字 III（劍指 Offer 56 - I. 數(shù)組中數(shù)字出現(xiàn)的次數(shù)）（找出兩個(gè)只出現(xiàn)一次的數(shù)字）

回想到，對所有數(shù)字進(jìn)行異或就可以得到結(jié)果，本題中其余數(shù)字也是出現(xiàn)兩次，區(qū)別在于有兩個(gè)數(shù)字只出現(xiàn)一次。在這里，我們會(huì)希望這兩個(gè)數(shù)字分別出現(xiàn)在兩組中，對這兩組都進(jìn)行異或，這樣就能得到答案了。怎么做呢？線索在于，對所有數(shù)字進(jìn)行異或后的結(jié)果，考慮其每一位取值的意義，如果為0，說明這兩個(gè)數(shù)字的這一位相同，如果為1則不相同。

找到第一位為1的，說明這兩個(gè)數(shù)在這一位上一個(gè)為1、一個(gè)為0。以此我們可以把數(shù)組分為兩部分，這兩個(gè)數(shù)各自存在于這兩部分中，劃分的依據(jù)就是這一位的取值。至于其他出現(xiàn)兩次的數(shù)，在分組時(shí)相同的數(shù)一定在同一組，因此對這兩組都進(jìn)行全部異或，出現(xiàn)兩次的數(shù)會(huì)抵消，最后剩下這兩個(gè)數(shù)字。

class Solution:def singleNumber(self, nums: List[int]) -> List[int]:# 全部異或ret = reduce(lambda x, y: x ^ y, nums) # reduce(二元函數(shù), 可迭代對象)h = 1while h & ret == 0: # 從右邊開始找第一位為1的（兩個(gè)數(shù)不同的位）h <<= 1a, b = 0, 0# 分別異或for n in nums:if n & h: # n 在這一位是 1，一個(gè)組a ^= nelse: # n 在這一位是 0，另一個(gè)組b ^= nreturn [a, b]

137. 只出現(xiàn)一次的數(shù)字 II（劍指 Offer 56 - II. 數(shù)組中數(shù)字出現(xiàn)的次數(shù) II）（劍指 Offer II 004. 只出現(xiàn)一次的數(shù)字 ）（找出一個(gè)只出現(xiàn)一次的數(shù)字，然而其他數(shù)字都出現(xiàn)三次）

class Solution:def singleNumber(self, nums: List[int]) -> int:counter = collections.Counter(nums)ans = [num for num, val in counter.items() if val == 1]return ans[0]

這一題用集合的話，還不能簡單地出現(xiàn)過就 pop，沒出現(xiàn)過就 push，因?yàn)橹貜?fù)數(shù)字是出現(xiàn)三次的，所以應(yīng)該用 Counter 來解決，更加優(yōu)化的思路是借鑒數(shù)字電路的：

class Solution:def singleNumber(self, nums: List[int]) -> int:a = 0b = 0for i in range(len(nums)):b = (b ^ nums[i]) & ~aa = (a ^ nums[i]) & ~breturn b

思路是設(shè)置一個(gè)狀態(tài)機(jī)，有 a、b 兩個(gè)記錄器：第一次碰到數(shù)字 x 時(shí)，記錄器 b 記錄下來，記錄器 a 為 0；第二次碰到數(shù)字 x 時(shí)，記錄器 a 記錄下來，記錄器 b 為 0；第三次碰到數(shù)字 x 時(shí)，兩個(gè)記錄器都為 0。這樣遍歷所有數(shù)字之后，出現(xiàn)三次的為 0，出現(xiàn)一次的就存放在記錄器 b 中。

實(shí)現(xiàn)記錄器 b 的方法：第一次碰到 x 記錄，第二次碰到 x 變 0，實(shí)際上就是異或 b = b ^ x，但是第三次碰到 x 時(shí) b 還是0，區(qū)別就只在于記錄器 a 的值為 x ，而第一二次時(shí) a 都為0，因此是 b = (b ^ x) & ~a ，對于記錄器 a 同理。

268. 丟失的數(shù)字（劍指 Offer 53 - II. 0～n-1中缺失的數(shù)字）（找出 0 - n 范圍中沒出現(xiàn)的那一個(gè)數(shù)）

class Solution:def missingNumber(self, nums: List[int]) -> int:n = len(nums)ans = 0for i in range(n):ans = ans ^ nums[i] ^ ians ^= (i + 1) # 正常的數(shù)組，包括 nreturn ans

方法一：正常的數(shù)組求和減去缺失的數(shù)組求和，差值就是缺失的數(shù)；

方法二：正常的數(shù)組與缺失的數(shù)組做異或，相同的數(shù)會(huì)異或?yàn)?，剩下的就是缺失的數(shù)。

448. 找到所有數(shù)組中消失的數(shù)字（找出多個(gè) 1 - n 范圍中沒出現(xiàn)的數(shù)）

class Solution:def findDisappearedNumbers(self, nums: List[int]) -> List[int]:n = len(nums)for num in nums:x = (num - 1) % n # 由于是表示下標(biāo)，所以 num - 1nums[x] += n # 加上 n 不會(huì)改變其對 n 取余數(shù)的結(jié)果ans = [i + 1 for i, num in enumerate(nums) if num <= n] # 沒有被加上 n 的下標(biāo)就是數(shù)組里沒有的return ans

由于是多個(gè)數(shù)沒出現(xiàn)，所以不能簡單地用異或解決，用集合固然可以做，但是更優(yōu)化地是把原數(shù)組本身作為集合，利用值與索引之間的映射關(guān)系來找出目標(biāo)數(shù)。此題中，我們把數(shù)組中出現(xiàn)了的值對應(yīng)的下標(biāo)都加上 n，則沒有被加上 n 的下標(biāo)就是數(shù)組里沒有的。

442. 數(shù)組中重復(fù)的數(shù)據(jù)（找出多個(gè) 1 - n 范圍中重復(fù)出現(xiàn)的數(shù)）

class Solution:def findDuplicates(self, nums: List[int]) -> List[int]:n = len(nums)for num in nums:x = (num - 1) % n # 由于是表示下標(biāo)，所以 num - 1nums[x] += n # 加上 n 不會(huì)改變其對 n 取余數(shù)的結(jié)果ans = [i + 1 for i, num in enumerate(nums) if num > n * 2] # 被加上2次 n 的下標(biāo)就是數(shù)組里重復(fù)的數(shù)return ans

與上一題同理，利用值與索引的對應(yīng)關(guān)系，找出在數(shù)組中出現(xiàn)兩次的值（其對應(yīng)下標(biāo)的值被兩次加上了 n）。

287. 尋找重復(fù)數(shù)（找出唯一的重復(fù)出現(xiàn)的數(shù)）

class Solution:def findDuplicate(self, nums: List[int]) -> int:left = 1right = len(nums) - 1while left < right:mid = left + (right - left) // 2 cnt = 0 # 記錄小于等于mid的元素個(gè)數(shù)for num in nums:if num <= mid:cnt += 1if cnt > mid:right = midelse:left = mid + 1return left

這題比較特別，規(guī)定了不能修改數(shù)組 nums 且只用常量級 O(1) 的額外空間。給定一個(gè)包含 n + 1 個(gè)整數(shù)的數(shù)組，其數(shù)字都在 1 到 n 之間，只有一個(gè)數(shù)字是重復(fù)的。因此，對于某個(gè)數(shù)字 x 來說，正常來說小于等于 x 的數(shù)字應(yīng)該有 x 個(gè)，例如有1、2、3、4共4個(gè)數(shù)字小于等于4，如果大于4了，則說明1、2、3、4其中有一個(gè)數(shù)字重復(fù)了，所以右邊界左移，反之左邊界右移。此為二分?jǐn)?shù)值型。

540. 有序數(shù)組中的單一元素（劍指 Offer II 070. 排序數(shù)組中只出現(xiàn)一次的數(shù)字）（找出有序數(shù)組的唯一不重復(fù)的數(shù)）

class Solution:def singleNonDuplicate(self, nums: List[int]) -> int:left = 0right = len(nums) - 1while left < right:mid = left + (right - left) // 2if mid % 2 == 1: # 只考慮偶數(shù)下標(biāo)mid -= 1if nums[mid] == nums[mid + 1]: # 如果它和下一個(gè)數(shù)相同，說明還正常，單一元素在右邊區(qū)間left = mid + 2else:right = midreturn nums[left]

這題用集合可以做到 O(n) 的時(shí)間，但是用二分可以做到 O(logn)。注意到，由于數(shù)組中只有一個(gè)不重復(fù)的數(shù)，所以總長度一定是奇數(shù)，而首尾下標(biāo)都為偶數(shù)。又因?yàn)閿?shù)組是有序的，所以重復(fù)數(shù)都是兩兩一起出現(xiàn)，且正常的情況都是（偶數(shù)索引，奇數(shù)索引），只有當(dāng)出現(xiàn)那一個(gè)不重復(fù)的數(shù)（偶數(shù)索引），索引才會(huì)變成（奇數(shù)，偶數(shù)）。所以用二分索引法找到每個(gè)偶數(shù)下標(biāo)，如果它和下一個(gè)數(shù)相同，則說明排序還是正常的，即單一元素在右邊區(qū)間；否則，則說明排序已經(jīng)不正常，單一元素在左邊區(qū)間。

41. 缺失的第一個(gè)正數(shù)（找出數(shù)組中沒有出現(xiàn)的最小的正整數(shù)）

class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n = len(nums)for i in range(n):if nums[i] <= 0:nums[i] = n + 1for i in range(n):num = abs(nums[i])if num <= n:nums[num - 1] = -abs(nums[num - 1])for i in range(n):if nums[i] > 0:return i + 1return n + 1

用集合可以做，但是題目要求時(shí)間復(fù)雜度為 O(n) 并且只使用常數(shù)級別額外空間。實(shí)際上，對于一個(gè)長度為 N 的數(shù)組，其中沒有出現(xiàn)的最小正整數(shù)只能在 [1, N+1] 中。這是因?yàn)槿绻?[1, N] 都出現(xiàn)了，那么答案是 N+1，否則答案是 [1, N] 中沒有出現(xiàn)的最小正整數(shù)。所以我們的思路就是：不考慮負(fù)數(shù)，將它們設(shè)置為 n + 1；對于在 [1, N] 中的數(shù)（此時(shí)之前的負(fù)數(shù)為 n + 1，不會(huì)被考慮），將其值對應(yīng)下標(biāo)的數(shù)變?yōu)樨?fù)（作為已經(jīng)出現(xiàn)過了的標(biāo)志）；最后找出第一個(gè)不是負(fù)數(shù)的，其對應(yīng)下標(biāo)就是沒出現(xiàn)的，即為答案。若所有都出現(xiàn)過，答案則為 n + 1。

總結(jié)

以上是生活随笔為你收集整理的在数组中找重复数、只出现一次的数或丢失数的题目（Leetcode题解-Python语言）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。