↓快轉到主要內容
  1. Leetcode/

[LeetCode] 442. Find All Duplicates in an Array

·
LeetCode hash table
目錄

題目連結：442. Find All Duplicates in an Array

解題思路
#

與 287. Find the Duplicate Number 題目很相似，皆是要求找出陣列中重複的數字。

這題一樣有些額外限制：

  • 時間複雜度為 O(n)。
  • 空間複雜度必須是 O(1)。

一開始看到這個題目有個 hash table Tag 我感到很疑惑，題目不是說必須使用 constant space 嗎，怎麼會使用 hash table？

原來是題目的測資有個奇妙的特性：

  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n

簡單來說就是陣列值 (value) 的範圍不會超過陣列的長度！因此我們可以使用原先的陣列來當作 hash table 來使用，使用陣列的值來當作 hash table 的索引 (index)：

  1. 在掃描的過程中，如果數字 nums[i] 是第一次出現，就把 nums[nums[i]] 的值變成負的，代表這個索引所表示的數字已經出現過了。
  2. 在迭代整個陣列時都透過 nums[i] 作為索引來查找該數字是否出現過 (如果查到的數是負數就表示先前出現過了)。
因為在過程中會改動到原始的陣列，因此應該要使用絕對值來存取陣列的值。

程式碼
#

C++
#

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;

        for (int i = 0; i < nums.size(); ++i) {
            int idx = abs(nums[i]) - 1;

            if (nums[idx] > 0)
                nums[idx] = -nums[idx];
            else
                res.push_back(abs(nums[i]));
        }

        return res;
    }
};

Python
#

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for i in range(len(nums)):
            idx = abs(nums[i]) - 1
            if nums[idx] > 0:
                nums[idx] = -nums[idx]
            else:
                res.append(abs(nums[i]))
        return res