Find All Numbers Disappeared in an Array

Posted on Edited on In Views:

448.Find All Numbers Disappeared in an Array

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

1
2
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

1
2
Input: nums = [1,1]
Output: [2]

时间复杂度：O(nlogn)
空间复杂度：O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int nums_size = nums.size();
        vector<int> ans_vec;
        int count = 1;
        for (int num : nums) {
            if (num < count)continue;
            else while(num > count) {
                ans_vec.push_back(count);
                count++;
            }
            count++;
        }
        while (count <= nums_size) {
            ans_vec.push_back(count);
            count++;
        }
        return ans_vec;
    }
};

原地修改：

时间复杂度：O(n)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        for (auto& num : nums) {
            int x = (num - 1) % n;
            nums[x] += n;
        }
        vector<int> ret;
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                ret.push_back(i + 1);
            }
        }
        return ret;
    }
};