LeetCode-面试题53-2-0到n-1中缺失的数字

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

示例1：

输入: [0,1,3]
输出: 2

示例2：

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

• 限制：

  1 <= 数组长度 <= 10000

解题思路

方法1、二分查找：

递增且数字范围在0~n-1的数组(有序数组)，数字和它对应的下标一定是相等的，缺失的数子会造成，该数字之后的数组下标在原本相等的情况下+1

排序数组中的搜索问题，首先想到二分查找解决

分析可知，数组可以分为左右子数组2部分：

• 左子数组：nums[i]=i
• 右子数组：nums[i]!=i

缺失的数字=右子数组的首位元素对应的索引

1. 初始化头尾指针start，end
2. 当start<end时，计算mid = (start+end)/2
3. 若nums[mid] = mid，则"右子数组的首位元素"一定在闭区间[mid+1,end]中，因此执行start = mid+1;
4. 若nums[mid]!=mid，则"左子数组的末位元素"一定在闭区间[start,mid-1]中，因此end = mid -1;
5. 跳出时，start就是指向右子数组的首位元素，end指向左子数组的末位元素，因此返回start即可

时间复杂度O(logN)，空间复杂度O(1)

方法2、异或运算：

异或运算，可以使得相同的数字异或为0，如b^b=0，a^b^b=a

由于数组有序且递增，除了缺失数字外，每一位元素和索引进行异或均为0

1. 初始化res=0，即先假设这个数字为0，先把数组的[0,n-1]范围内的数组异或一遍，此时等于n个数字全部异或，再把他和对应的[0,n-1]索引下标异或一遍，这两个操作可以在一个循环中搞定。
2. 因为元素和下标是相等的，异或为0，所以缺失的数字一定会在异或2次操作后剩下，因为缺失的数字和下标是不等的
3. 最后再将res异或上数组下标n也就是此时i的值(因为此时，数组已经异或了n个，而下标只异或了n-1个，所以循环之外还需要再次异或数组下标i++即n)，就可以得到缺失的数字。

Java代码1

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

Java代码2

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i=0;i<nums.length;i++){
            res^=nums[i];
            res^=i;
        }
        return res^n;
    }
}

方法、异或运算：

数组无序的情况依旧可以使用异或运算进行处理

先初始化r=0，将r与数组所有值异或一次，之后将r和数组i+1异或一次(因为下标从1开始，但循环从0开始)，由于补全之后，数组的长度是n，当前的数组长度为n-1，所以还需要再异或最后一位数字的索引，因为数组的范围从1开始，所以最后的异或同样有1的偏移，即nums.length+1，才能得到缺失的数字。

无论数组是否有序，异或2次之后，缺失的数字就是剩下的，如果不缺失则2次异或完毕的结果为0

Java代码3

public class LeetCode53_2 {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, 2, 5, 4, 7, 8};
        int r = 0;
        for (int i = 0; i < nums.length; i++) {
            r ^= (nums[i] ^ (i+1));
        }
        System.out.println(r ^ (nums.length+1));
    }
}