leetcode解题: Find All Numbers Disappeared in an Array (448)

发表于 | 分类于

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： O（N) Time + O(1) Space

本题是用了替换的办法。由于提前知道数的范围是从1 ~ n， 那么我们可以试着把每一个数放到该存在的位置，也就是nums[i] = i + 1。 不停的调整每一个位置上的数，直到满足这个条件或者是和要调整的位置上的数相等。
由于每一个数只visit一次，所以complexity是O（N）。
比较tricky的是，在置换两个数的时候要特别小心，我一开始写了

1
2
3
int ex = nums[i];
nums[i] = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];

这是不对的，因为在第二步nums[i]的值已经换过了。
等扫描结束一遍之后，再扫描一遍vector找出位置上的数和位置不同的数。
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int i = 0;
        while (i < nums.size()) {
            if (nums[i] - 1 != i) {
                int temp = nums[nums[i] - 1];
                if (temp == nums[i]) {
                    ++i;
                } else {
                    nums[nums[i] - 1] = nums[i];
                    nums[i] = temp;
                }
            } else {
                ++i;
            }
        }
        
        vector<int> res;
        for (int j = 0; j < nums.size(); ++j) {
            if (nums[j] - 1 != j) {
                res.push_back(j + 1);
            }
        }
        return res;
    }
};

Java

1