Cinte's Leetcode Record
0%

448. Find All Numbers Disappeared in an Array

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

448. Find All Numbers Disappeared in an Array

抄的discussion

使用原数列中的坐标是否为负来表征当前坐标所代表的值是否存在。由此使得S(n) = O(n)

聪明啊！

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) {
        for(int i = 0; i < nums.size(); ++i)
        {
            // 下述操作也类似一个哈希表
            int m = abs(nums[i]) - 1; // 当前的数字，对应的角标，由于可能之前被操作为负的，所以要绝对值
            nums[m] = nums[m] > 0 ? -nums[m] : nums[m];  // 角标对应过去的为负，表示那个被记录到了
        }
        vector<int> ret;
        for(int i = 0; i < nums.size(); ++i)
        {
            if(nums[i] > 0)
                ret.push_back(i + 1);
        }
        return ret;
    }
};
review
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> ret;
        int n = nums.size() + 1;
        for(int i = 0; i < n - 1; ++i)
            while(i + 1 != nums[i] && nums[i] != nums[nums[i] - 1])
                swap(nums[i], nums[nums[i] - 1]);
        for(int i = 1; i < n; ++i)
            if(i != nums[i - 1])
                ret.push_back(i);
        return ret;
    }
};
review2
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> ret;
        int n = nums.size() + 1;
        for(auto num : nums)
            nums[(num - 1) % n] += n;
        for(int i = 1; i < n; ++i)
            if(nums[i - 1] <= n)
                ret.push_back(i);
        return ret;
    }
};