[LeetCode] #442. Find All Duplicates in an Array

題目

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

直覺解

構想：

用 seen 把出現過的數字存起來。如果遇到已經在 seen 裡面的數字，那就是重複的（不符合 uses only constant extra space）。

python 3 實作：

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        ans = []
        seen = {}
        
        for num in nums:
            if num not in seen:
                seen[num] = True
            else:
                ans.append(num)
        return ans

效能：

Runtime: 351 ms, faster than 76.63% of Python3 online submissions for Find All Duplicates in an Array.
Memory Usage: 22.8 MB, less than 19.60% of Python3 online submissions for Find All Duplicates in an Array.

研究別人的解

來源：sample 308 ms submission

構想：List comprehension 和 set（不符合 uses only constant extra space）

別人的 python 3 實作：

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        seen = set()
        return [x for x in nums if x in seen or seen.add(x)]

效能：

第一次
Runtime: 613 ms, faster than 5.03% of Python3 online submissions for Find All Duplicates in an Array.
Memory Usage: 23.2 MB, less than 14.78% of Python3 online submissions for Find All Duplicates in an Array.

第二次
Runtime: 470 ms, faster than 12.06% of Python3 online submissions for Find All Duplicates in an Array.
Memory Usage: 23.1 MB, less than 14.78% of Python3 online submissions for Find All Duplicates in an Array.

第三次
Runtime: 336 ms, faster than 90.74% of Python3 online submissions for Find All Duplicates in an Array.
Memory Usage: 23 MB, less than 16.83% of Python3 online submissions for Find All Duplicates in an Array.

第四次
Runtime: 320 ms, faster than 99.25% of Python3 online submissions for Find All Duplicates in an Array.
Memory Usage: 23.2 MB, less than 14.78% of Python3 online submissions for Find All Duplicates in an Array.

研究別人的解

來源：Alpha Campe LeetCode 訓練營講師 Wesley

構想：用「nums[a-1] 這個數字是負數」來紀錄「a 數字出現過了」。

因為有下列 Constraints，才能用這種方式紀錄。

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n
• Each element in nums appears once or twice.

如果 nums 中有 0，0 的負數依然是零，就認不出 0 的 index 代表的數字到底有沒有出現過。如果 nums 中有負數，就沒辦法判斷，是本來就負數，還是為了記錄「index + 1」這個數字出現過才變成負數。

如果數字超過 nums index 的範圍，nums 的 index 就不夠用了。

這個紀錄方式只能確保「數字至少出現一次」，沒辦法精準辨認「到底出現幾次」。題目要求的是「只列出出現兩次的數字」，如果數字可能會出現兩次以上，這個方法就行不通。

別人的 javascript 實作：

// Stored in original array, 62% ~ 98%
var findDuplicates = function(nums) {
    var res = [];
    for(let i = 0; i < nums.length; i++){
        var n = Math.abs(nums[i]);
        var index = n-1;
        if (nums[index] < 0) {
            res.push(n);
        } else {
            nums[index] *= -1;
        }
    }
    return res;
};

效能：

第一次
Runtime: 112 ms, faster than 72.29% of JavaScript online submissions for Find All Duplicates in an Array.
Memory Usage: 47 MB, less than 75.95% of JavaScript online submissions for Find All Duplicates in an Array.

第一次
Runtime: 146 ms, faster than 29.47% of JavaScript online submissions for Find All Duplicates in an Array.
Memory Usage: 46.8 MB, less than 80.35% of JavaScript online submissions for Find All Duplicates in an Array.

模仿別人的解

構想：用「nums[a-1] 這個數字是負數」來紀錄「a 數字出現過了」。

python 3 實作：

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        ans = []
        for num in nums:
            num = abs(num)
            index = num - 1
            if nums[index] > 0:
                nums[index] *= -1
            else:
                ans.append(num)
        return ans

效能：

Runtime: 364 ms, faster than 61.04% of Python3 online submissions for Find All Duplicates in an Array.
Memory Usage: 21.9 MB, less than 55.19% of Python3 online submissions for Find All Duplicates in an Array.

相關資料：Leetcode 刷題 pattern - Cyclic Sort

---

最後更新日期： 2021 年 9 月 2 日