摘要

剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

一、二分法

排序数组中的搜索问题，首先想到二分法解决。根据题意，数组可以按照以下规则划分为两部分。

左子数组： nums[i]=i；
右子数组： nums[i]≠i ；

缺失的数字等于“右子数组的首位元素” 对应的索引；考虑使用二分法查找 “右子数组的首位元素”。

算法解析：

初始化：左边界 i=0，右边界 j=len(nums)−1；代表闭区间 [i,j] 。
循环二分：当 i≤j时循环（即当闭区间 [i,j]为空时跳出）；
计算中点 m=(i+j)//2 ，其中 "//" 为向下取整除法；
若 nums[m]=m ，则 “右子数组的首位元素” 一定在闭区间 [m+1,j]中，因此执行 i=m+1；
若 nums[m]≠m ，则 “左子数组的末位元素” 一定在闭区间 [i,m−1]中，因此执行 j=m−1；
返回值：跳出时，变量i 和j分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” 。因此返回i即可。

class Solution {public int missingNumber(int[] nums) {int i = 0, j = nums.length - 1;while(i <= j) {int m = (i + j) / 2;if(nums[m] == m) i = m + 1;else j = m - 1;}return i;}
}

复杂度分析：

时间复杂度 O(logN)：二分法为对数级别复杂度。
空间复杂度 O(1)：几个变量使用常数大小的额外空间。

二、位运算

数组 nums中有n−1个数，在这 n−1个数的后面添加从0 到 n−1的每个整数，则添加了n个整数，共有 2n−1个整数。

在 2n−1个整数中，缺失的数字只在后面n个整数中出现一次，其余的数字在前面n−1个整数中（即数组中）和后面 n个整数中各出现一次，即其余的数字都出现了两次。

根据出现的次数的奇偶性，可以使用按位异或运算得到缺失的数字。按位异或运算⊕满足交换律和结合律，且对任意整数 x都满足x⊕x=0和x⊕0=x。

由于上述 2n−1个整数中，缺失的数字出现了一次，其余的数字都出现了两次，因此对上述 2n−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;}
}

复杂度分析