0~n-1中缺失的数字

78 阅读 0 评论 52 点赞

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

概述

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

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

代码实现：

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;
    }
};