Java1(二分)
时间复杂度:$O(logn)$
空间复杂度:$O(1)$
思路: 参考了yxc题解
缺失的数x之前的数是与数组下标一一对应的($[0, x - 1]$),而之后的数(包括他自己)是不与下标一一对应的。即数组左边蓝色部分都满足nums[i] == i
,数组右边橙色部分都不满足nums[i] == i
,因此我们可以二分出分界点 $x$ 的值。特殊情况:当所有数都满足
nums[i] == i
时,表示缺失的是n
。
class Solution {
public int getMissingNumber(int[] nums) {
if(nums.length < 1) return 0;
int l = 0, r = nums.length - 1;
while(l < r) {
int mid = l + r >> 1;
if(nums[mid] != mid) r = mid;
else l = mid + 1;
}
return l == nums[l] ? l + 1 : l;
}
}
Java2(异或)
时间复杂度:$O(n)$
空间复杂度:$O(1)$
思路:
由于异或的性质,
a^a = 0
0^a=a
a^a^b=b
我们可以将数组下标异或数组元素,最后再异或数组长度即可得到缺失的数字。如果没缺数字,异或的最终值即数组的长度。
例子1:[0,1,2,4]
异或过程:0 ^ (0^0) ^ (1^1) ^ (2^2) ^ (3^4) ^ 4 == 3
例子2:[0,1,2,3,4]
异或过程:0 ^ (0^0) ^ (1^1) ^ (2^2) ^ (3^3) ^ (4^4) ^ 5 == 5
class Solution {
public int getMissingNumber(int[] nums) {
int ans = 0;
for(int i = 0; i < nums.length; ++i) {
ans ^= i ^ nums[i];
}
return ans ^ nums.length;
}
}
Java3(求和取差值)
时间复杂度:$O(n)$
空间复杂度:$O(1)$
思路:
缺失的数字为完整数组所有数之和与当前数组所有数之和的差值。
class Solution {
public int getMissingNumber(int[] nums) {
int sum = 0;
for(int i : nums) sum += i;
int n = nums.length;
return n * (n + 1) / 2 - sum;
}
}
Java4(寻找与数组下标不匹配的数)
时间复杂度:$O(n)$
空间复杂度:$O(1)$
思路:
如果当前数组下标与当前数不相同,说明缺失的是当前数组下标的数。
特殊情况就是数组是完整的,直接返回第n个数就行。
class Solution {
public int getMissingNumber(int[] nums) {
if(nums.length < 1) return 0;
for(int i = 0; i < nums.length; ++i) {
if(i != nums[i]) return i;
}
return nums.length;
}
}
二分是最屌的
试了一下 取或的方法需要判空
if(nums.length < 1) return 0;
不然会有Seg Fault
不好意思 java里面可以 我用的c++ 才会出这种问题