LeetCode#442 Find All Duplicates in an Array

問題

給一個長度為 n 的整數陣列，裡面的元素由 1~n 所組成，每個數字出現 0~2 次，找出所有出現 2 次的數字。(不使用額外空間且時間複雜度必須為O(n))

輸入

[4, 3, 2, 7, 8, 2, 3, 1]

輸出

[2, 3]

方法

負號標記法
將陣列nums的值遍歷一次，將每個出現過的值當作index，將對應到的num[index]的值乘上-1，若對應到的值已經為負數的話，代表已經出現過 1 次，目前是第 2 次，這樣就能找出所有出現過 2 次的元素了。

1
2
3
4
5
6
7
8
9

class Solution(object):
    def findDuplicates(self, nums):
        ans = []
        for i in nums:
            if nums[abs(i) - 1] < 0:
                ans.append(abs(i))
            else:
                nums[abs(i) - 1] *= -1
        return ans

#448 Find All Numbers Disappeared in an Array，也可以用同樣的方法來解。