Missing Number

Posted on Edited on In Views:

268.Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

1
2
3
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

1
2
3
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

1
2
3
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

排序法：

时间复杂度：O(nlogn)

空间复杂度：O(1)

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

哈希表：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> hash;
        int nums_size = nums.size();
        for (int i = 0; i < nums_size; i++) {
            hash.insert(nums[i]);
        }
        int missing = -1;
        for (int i = 0; i <= nums_size; i++) {
            if (!hash.count(i)) {
                missing = i;
                break;
            }
        }
        return missing;
    }
};

数学：

时间复杂度：O(n)

空间复杂度：O(1)

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

位运算：

时间复杂度：O(n)

空间复杂度：O(1)

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