政子的博客

技术|学习|随笔

LeetCode-Find All Numbers Disappeared in an Array

题目要求使用 O(1)的空间复杂度和 O(n)的时间复杂度来解决问题，所以不能使用排序或者 map 的方法。

因为数组中的数字是从 1 到 n 的，所以这和Find All Duplicates in an Array中的解法很类似，先将数组尽量摆放在合适的位置上（数字 i 对应数组中的位置 i-1），然后在统计一遍不在合适位置上的数字即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> result;
        for(int i=0;i<nums.size();i++){
            while(nums[i]!=i+1 && nums[nums[i]-1]!=nums[i]){
                int j=nums[i]-1;
                int t=nums[i];
                nums[i]=nums[j];
                nums[j]=t;
            }
        }
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=i+1) result.push_back(i+1);
        }
        return result;
    }
};

顺着 Find All Duplicates in an Array 中的思路，因为数组中的所有数字都是正数，所以可以在数组中将某位置原数字变为负数来表示该位置中的数字已经出现过。具体过程：第一次遇到某个数字的时候将对应位置的数字变成其相反数，然后第二次扫描数组的时候，找到非负数的地方即可（这样就不用像前面方法那样每次都交换元素，所以会快很多）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> result;
        for(int i=0;i<nums.size();i++){
            int j=abs(nums[i])-1;
            if(nums[j]>0) nums[j]*=-1;
        }
        for(int i=0;i<nums.size();i++){
            if(nums[i]>0) result.push_back(i+1);
        }
        return result;
    }
};