題目： LeetCode - 442. Find All Duplicates in an Array

題目說明

給一個陣列 nums，1 ≤ nums[i] ≤ n。求此陣列中出現兩次的數字。
※ 題目希望時間複雜度為 O(n)，且不使用額外的空間。

解題思路

由於有 1 ≤ nums[i] ≤ n 這個條件，所以我們可以使用陣列元素的正負來判斷此數字是否出現過。具體作法為使用一個迴圈遍歷陣列，我們先判斷 nums[abs(nums[i]) - 1] 是否為負數，若為負數代表前面出現過，否則將 nums[abs(nums[i]) - 1] 設為負數。
※ 使用 abs() 是為了避免這個元素已經被設為負數，減一是因為 nums[i] 的範圍為 [1, n]。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        vector<int> v;
        for(auto num : nums)
            if(nums[abs(num) - 1] < 0)
                v.push_back(abs(num));
            else
                nums[abs(num) - 1] *= -1;
        return v;
    }
};