jz053II.0~n-1中缺失的数字

题目链接

这个问题有一个直观的解决方案，我们可以先用公式n（n-1）/2求出数字0～n-1的所有数字之和，记为s1。接着求出数组中所有数字的和，记为s2。那个不在数组中的数字就是s1-s2的差。这种解法需要O（N）的时间求数组中所有数字的和。显然，该解法没有有效利用数组是递增排序的这一特点。

因为0～n-1这些数字在数组中是排序的，因此数组中开始的一些数字与它们的下标相同。也就是说，0在下标为0的位置，1在下标为1的位置，以此类推。如果不再数组中的数字记为m，那么所有比m小的数字的下标都与它们的值相同。由于m不在数组中，那么m+1处在下标为m的位置，m+2处在下标为m+1的位置，以此类推。我们发现m正好是数组中第一个数值和下标不相等的下标，因此这个问题转化成在排序数组中找出第一个值和下标不相等的元素。我们可以基于二分查找的算法用如下过程查找：如果中间元素的值和下标相等，那么下一轮查找只需要查找右半边；如果中间元素的值和下标不相等，并且它前面一个元素和它的下标相等，这意味着这个中间的数字正好是第一个值和下标不相等的元素，它的下标就是在数组中不存在的数字；如果中间元素的值和下标不相等，并且它前面一个元素和它的下标也不相等，这意味着下一轮查找我们只需要在左半边查找即可。下面是基于二分查找法的代码。这个算法的时间复杂度是O（logN），空间复杂度是O（1）。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] == m:
                i = m + 1
            else: 
                j = m - 1
        return i