【Java面试真题】剑指Offer53.2——0~n-1中缺失的数字（异或、二分两种解法）

【Java实现】剑指Offer53.2——0~n-1中缺失的数字：面试真题，两种思路分享

前面有另一道面试题 【Java实现】剑指offer53.1——在排序数组中查找数字（LeetCode34：在排序数组中查找元素的起始位置）
都是二分类型的，可以借鉴一下思路

题意解析：

这道题很特别，所有的测试用例都很有特点，都是形如[0,1,2,3,5,6,7]这样的，突然跳跃这个数值的 索引 ，即是问题的解

具体如下：

• 前半部分数组中：索引和数值相等
• 后半部分数组中：索引比数值小1

第一种：二分思想

不同于以往的二分查找，这里二分法直接比较索引、数值这两者，来找到缺失的那个值，设索引为 index ，数值为 nums[index] ：

• 如果 nums[index] > index ，则说明该 index 或其前方存在解（缺值）
• 反之，说明解在该值的后方

因此，二分查找的步骤如下：

• 确定边界 i,j ，获取 mid 索引
• 判断 mid 索引和其对应数值的关系，并参照上述步骤进行循环
• 跳出循环后， i 所在的索引位置即为解

二分解法代码：

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

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

第二种：异或思想

异或运算中，同一个数异或的值为0：例如： 5 ^ 5 = 0 ； a ^ b ^ b = a

根据题意，让数组元素与索引进行异或，如果相同，则结果为 0 相互抵消，最后与长度 n-1 异或。由于 0~n-1 共 n 个数，存在抵消不掉的情况，最后形成形式： a ^ b ^ a ；结果就是缺少的那个数 b

异或解法代码：

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

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

复杂度分析：

1. 异或：时间O(n)，空间O(1)
2. 二分：时间O(logn)，空间O(1)

异或方法虽然很快，但是其复杂度是高于二分法的，在数据量很大的时候推荐使用二分法。