442. Find All Duplicates in an Array

題目描述

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

給定一個長度為 n 的整數陣列，其中陣列中的數字在1到n之間（包括1和n），並且有些元素會重複出現，找到所有出現兩次的元素，並返回這些元素的陣列

限制條件

• 你必須在沒有額外空間的情況下實現這個解決方案（O(1) 空間複雜度）
• 時間複雜度應該是 O(n)

解題思路

此題要求找到所有重複的數字，並且要求解決方案的空間複雜度為 O(1)。因此，我們不能使用額外的陣列或集合來存儲數字。為了達到這一要求，我們可以利用原陣列本身來標記已經出現過的數字

• 由於需要保留原數字且陣列中數字皆為正數，可以將數字轉為負值來記錄

具體步驟如下：

1. 遍歷陣列中的每一個數字
2. 對於每個數字，取其絕對值並減一得到索引 i
3. 將陣列中索引 i 處的數字取負值以標記該索引已經出現過
4. 如果索引 i 處的數字已經是負數，表示該索引的數字已經出現過一次，此時將該數字添加到結果陣列中

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        const int n = nums.size();
        vector<int> ans;

        for (const int num : nums) {
            const int i = abs(num) - 1;
            nums[i] *= -1;
            if (nums[i] > 0) {
                ans.push_back(abs(num));
            }
        }
        return ans;
    }
};

複雜度分析

• 時間複雜度：O(n)，其中 n 是陣列的長度。我們只需遍歷陣列一次
• 空間複雜度：O(1)，除了結果外，沒有使用額外的空間