0~n-1中缺失的数字

110 阅读 0 评论 73 点赞

我是靠谱客的博主爱笑乌冬面，这篇文章主要介绍0~n-1中缺失的数字，现在分享给大家，希望可以做个参考。

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

思路描述：对于这道题，我们首先想到的就是暴力破解，遍历一边找出来，但是如果数组很大的话，这样的时间复杂度就太高了。注意题目：递增排序数组，并且数组元素全部唯一且是从0开始的，那么数组元素应该等于对应的下标。既然是这样。我们可以直接找到数组中间节点，判断nums[mid]==mid;如果相等，说明前半部分没有缺失元素，去后半部分找，否则，反之。

代码实现：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int left=0;
        int right=nums.size()-1;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(nums[mid]==mid)left=mid+1;
            else
               right=mid-1;
        }
        return left;
    }
};