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

首先观察题目给我们的条件，有序递增数组中找元素，比较自然地会往二分上联系。一般的二分，我们找到答案后会直接返回，但这里的二分，我们需要不断缩小空间，直到找到为止。

class Solution {
    public int missingNumber(int[] nums) {
        int l= 0;
        int r= nums.length - 1;
        while (start < end) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == mid) {
                //如果nums[mid] == mid也就是说当前元素的
                //下标等于他自己，比如数组[0,1,2,3,4,5]每
                //个元素的下标都等于他自己，说明[l,mid]
                //没有缺少任何数字，那么缺少的肯定是在[mid+1,r]
                l = mid + 1;
            } else {
                //如果当前元素的下标不等于他自己，比如[0,1,2,4]中
                //nums[3]==4，说明说明缺少的数字就在这个区间内
                r = mid;
            }
        }
        //如果类似于[0,1,2,3]这种start指向了数组的最后一个，我们让他加1
        return l == nums[l] ? l + 1 : l;
    }
}

二分的时间复杂度为\(O(nlogn)\),空间复杂度为\(O(1)\)。
再分析时间复杂度更低的算法，由于每个数字都只出现了一次，由此考虑位运算，先从0-n之间的所有数异或，再与原数组中的数字异或一次，这样得到的结果即为丢失的数字。

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