题目描述
题目链接:268. Missing Number
Given an array
nums
containingn
distinct numbers in the range[0, n]
, return the only number in the range that is missing from the array.
例子
例子 1
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.
例子 2
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.
例子 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.
Follow Up
- Could you implement a solution using only
O(1)
extra space complexity andO(n)
runtime complexity?
Constraints
n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
- All the numbers of
nums
are unique.
解题思路
这道题和 [Leetcode]136. Single Number(C++) 类似,同样可以利用异或的性质求解,在 136 中已经给定了成对的数字需要找出只有一个数字,这里我们可以先将 1 ~ n 的数字异或成一个数字,再和数字中的 n 个数字异或这样相同的数字会抵消掉,剩下的就是数组中缺失的数了。代码如下:
#include <vector>
class Solution {
public:
int missingNumber(std::vector<int>& nums) {
int mask = 0;
for (int i = 0; i <= nums.size(); ++i) {
mask ^= i;
}
for (int num : nums) {
mask ^= num;
}
return mask;
}
};
- 时间复杂度:
O(n)
- 空间复杂度:
O(1)
GitHub 代码同步地址: 268.MissingNumber.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions