問題
問題描述：給定一個整數(shù)數(shù)組，1 <= a[i] <= n，其中 n 為數(shù)組長度。有些元素出現(xiàn) 2 次，有些只出現(xiàn) 1 次，請找出所有出現(xiàn) 2 次的元素。
要求：在 O(n) 的時間內(nèi)，并不使用額外的空間。
栗子：
輸入：
[4,3,2,7,8,2,3,1]
輸出：
[2,3]
想看英文的戳這里：原題地址
解題思路
如何判斷出現(xiàn)了 2 次呢？
按常規(guī)思路，可以用額外的數(shù)組或者 map 來記錄元素出現(xiàn)的次數(shù)，這樣實現(xiàn)起來比較簡單。比如用數(shù)組 count[] 來記錄次數(shù)。
// 初始化 count[n] = 0，count 中有 n 個元素。
// 記錄每個數(shù)字出現(xiàn)的次數(shù)
count[a[i] - 1] += 1
但是題目要求不使用額外的空間，所以只能在數(shù)組 a[] 上做文章。
同時可以借鑒常規(guī)思路的做法，在 a[i] 出現(xiàn)時，將其標(biāo)記為已出現(xiàn)。由于 a[i] 全為正整數(shù)，所以我們可以想到一個比較取巧的方式，就是將 a[i] 對應(yīng)位置的數(shù)標(biāo)記成 對應(yīng)的負(fù)數(shù), 即 a[a[i]-1] *= -1。當(dāng)再次遇到 a[i] 時，如果其對應(yīng)的數(shù)已經(jīng)為負(fù)數(shù)，則可判斷為重復(fù)。
那么有個問題來了，如果遍歷過程中遇到之前標(biāo)記的負(fù)數(shù)了，怎么辦？很簡單，只要取 abs(a[i]) 即可。
步驟圖解
- 初始狀態(tài)
QQ20190410-0.png
-
遍歷 4，a[3] = -7
QQ20190410-1.png 遍歷 3，a[2] = -2
QQ20190410-2.png
- 遍歷 2，a[1] = -3
QQ20190410-3.png
- 遍歷 7，a[6] = -3
QQ20190410-4.png
- 遍歷 8，a[7] = -1
QQ20190410-5.png
- 遍歷 2，a[1] 已經(jīng)為負(fù)數(shù)，則表示重復(fù)
QQ20190410-6.png
- 遍歷 3，a[2] 已經(jīng)為負(fù)數(shù)，則表示重復(fù)
QQ20190410-7.png
- 遍歷 1，a[0] = -1，結(jié)束。
QQ20190410-8.png
代碼實現(xiàn)
python 代碼如下：
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
res = []
// 逐個遍歷，將 num 所對應(yīng)的 index 設(shè)置為負(fù)數(shù)。
for num in nums:
positiveNum = abs(num)
// 已經(jīng)置為負(fù)數(shù)，說明有相同的數(shù)
if nums[positiveNum-1] < 0:
res.append(positiveNum)
else:
nums[positiveNum-1] *= -1
return res
