題目網址：https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/

題意：原本有一包含 [1, n] 總共 n 個數的 array, 今給一個 n 個數的 array (含重複數) nums, 找出所有缺失的數。

Solution：

想法：將數字設為 負數 來標記我們看到的數字的 index, 然後遍歷 nums 元素, 若 nums[i] > 0, 代表數字 i + 1 沒出現過

e.g. [1, 2, 2] ➔ [-1, -2, 2], 其中 nums[0] 紀錄數字 1 是否出現

因為數字 1 有出現, 所以 nums[0] 被設為負數, 依此類推

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        // 將數字設為負數來標記我們看到的數字的index
        for (const auto& num : nums) {
            nums[abs(num) - 1] = -abs(nums[abs(num) - 1]);
        }

        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0) {
                res.emplace_back(i + 1);
            }
        }
        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(1)$ ➔ 扣除返回的 array, 且缺失 idx 都儲存在 nums 中, 故只需常數空間