剑指 Offer 53 - II. 0～n-1中缺失的数字
题目：
思路：
【1】最简单的直接遍历的方式：这个思路是基于，首先一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内，这就说明了这是一串连续的数字，且会与下标有一定联系，当不缺失的时候，下标与数值一 一对应，故直接遍历且比对下标即可。
【2】基于最简单的方式的理念，还可以使用Set辅助空间做也行，使用异或位运算进行两次遍历都可以，但是这样其实不如最简单的办法。
【3】当然其实这种有序的其实最好的优化其实是考虑二分查找。
代码展示：
基于二分查找的优化：
//时间0 ms击败100%
//内存42.4 MB击败35.37%
class Solution {
public int missingNumber(int[] nums) {
int l = 0;
int r = nums.length - 1;
while(l <= r){
int mid = l + (r - l) / 2;
if(nums[mid] == mid){
l = mid + 1;
}else{
r = mid - 1;
}
}
return l;
}
}基于最直接的方式衍生出来的：
//使用辅助空间的方式：
//时间3 ms击败4.31%
//内存41.7 MB击败98.20%
//时间复杂度：O(n)，遍历数组 nums 将元素加入哈希集合的时间复杂度是 O(n)，遍历从 0 到 n−1的每个整数并判断是否在哈希集合中的时间复杂度也是 O(n)，故是 O(2n) 等于O(n)。
//空间复杂度：O(n)，哈希集合中需要存储 n−1 个整数。
class Solution {
public int missingNumber(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
int n = nums.length + 1;
for (int i = 0; i < n - 1; i++) {
set.add(nums[i]);
}
int missing = -1;
for (int i = 0; i <= n - 1; i++) {
if (!set.contains(i)) {
missing = i;
break;
}
}
return missing;
}
}
//使用位运算的方式
//时间0 ms击败100%
//内存42.5 MB击败14.24%
//时间复杂度：O(n)，需要对 2n−1 个数字计算按位异或的结果。
//空间复杂度：O(1)。
class Solution {
public int missingNumber(int[] nums) {
int xor = 0;
int n = nums.length + 1;
for (int i = 0; i < n - 1; i++) {
xor ^= nums[i];
}
for (int i = 0; i <= n - 1; i++) {
xor ^= i;
}
return xor;
}
}最简单的直接遍历的方式：
//时间0 ms击败100%
//内存42.4 MB击败26.47%
//时间复杂度：O(n)，其中 n 是数组 nums 的长度加 1。需要遍历数组 nums 一次寻找缺失的数字。
//空间复杂度：O(1)。
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length + 1;
for (int i = 0; i < n - 1; i++) {
if (nums[i] != i) {
return i;
}
}
return n - 1;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-02-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
