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:
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:
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:
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.
Constraints:
- n == nums.length
- 1 <= n <= 104
- 0 <= nums[i] <= n
- All the numbers of nums are unique.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
位运算
class Solution {
public int missingNumber(int[] nums) {
int res=0;
for(int i=0;i<nums.length;i++){
res^=(i+1)^nums[i];
}
return res;
}
}等差数列(加法交换律和结合律)
class Solution {
public int missingNumber(int[] nums) {
int res=0;
int n = nums.length;
int sum = (n+1)*n /2;
for(int i=0;i<nums.length;i++){
res+=nums[i];
}
return sum-res;
}
}等差数列-防止溢出
class Solution {
public int missingNumber(int[] nums) {
int res = nums.length;
for(int i=0;i<nums.length;i++){
res+=(i-nums[i]);
}
return res;
}
}HashSet-空间复杂度O(n)
class Solution {
public int missingNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int i=0;i<nums.length;i++){
set.add(nums[i]);
}
for(int i=0;i<nums.length;i++){
if(!set.contains(i)){
return i;
}
}
return nums.length;
}
}