448 Find All Numbers Disappeared in an Array 找到所有數(shù)組中消失的數(shù)字

Description:
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

題目描述:
給定一個范圍在 1 ≤ a[i] ≤ n ( n = 數(shù)組大小 ) 的 整型數(shù)組欢嘿，數(shù)組中的元素一些出現(xiàn)了兩次，另一些只出現(xiàn)一次荧嵌。

找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數(shù)組中的數(shù)字娩缰。

您能在不使用額外空間且時間復雜度為O(n)的情況下完成這個任務嗎? 你可以假定返回的數(shù)組不算在額外空間內(nèi)赤兴。

示例：

輸入:
[4,3,2,7,8,2,3,1]

輸出:
[5,6]

思路:

用出現(xiàn)過的數(shù)字對應下標, 將下標對應的數(shù)組元素改為負數(shù)
遍歷第二次找出所有正數(shù)
時間復雜度O(n), 空間復雜度O(1)

代碼:
C++:

class Solution 
{
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) 
    {
        for (int i = 0; i < nums.size(); i++) nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1]);
        vector<int> result;
        for (int i = 0; i < nums.size(); i++) if (nums[i] > 0) result.emplace_back(i + 1);
        return result;
    }
};

Java:

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int i = 0; i < nums.length; i++) nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1]);
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) result.add(i + 1);
        }
        return result;
    }
}

Python:

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        return list(set(range(1, len(nums) + 1))- set(nums)) if nums else []