Cinte's Leetcode Record
0%

268. 丢失的数字

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

268. 丢失的数字

类似于hash的一种解法
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        nums.emplace_back(0);
        int n = nums.size();
        for(auto num : nums)
            nums[num % n] += n;
        for(int i = 0; i < n; ++i)
            if(nums[i] < n)
                return i;
        return 0;
    }
};

O(n)

O(1)

排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if(nums.front() != 0)
            return 0;
        if(nums.back() != n)
            return n;
        for(int i = 0; i < n; ++i)
            if(nums[i] != i)
                return i;
        return 0;
    }
};

O(nlogn)

O(1)

异或

0~n的所有数字异或一遍，nums中的数字再异或一遍，剩下的就是只出现一次的，也就是只missing一次的。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int ret = n;
        for(int i = 0; i < n; ++i)
            ret ^= nums[i] ^ i;
        return ret;
    }
};

O(n)

O(1)

数学
1
2
3
4
5
6
7
8
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int sum = n * (n + 1) / 2;
        return sum - accumulate(nums.begin(), nums.end(), 0);
    }
};