【剑指 Offer II】 0～n-1中缺失的数字

Knous

于 2022-09-03 20:53:04 发布

阅读量232

点赞数

分类专栏：每日练习文章标签：开发语言 c++

本文链接：https://blog.csdn.net/qq_60306111/article/details/126682362

版权

每日练习专栏收录该内容

21 篇文章

订阅专栏

本文探讨了两种解决数组中缺失数字的方法，包括简单的暴力搜索和高效的二分查找策略。暴力方法通过遍历数组，检查每个元素是否与其索引匹配，找到第一个不匹配的索引即为缺失值。二分查找则通过不断缩小范围，最终确定缺失数字的位置。这两种方法在不同场景下各有优势，适合不同的性能需求。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

细说这题，其实有多种办法，这里讲两种，多的有兴趣可以自己想想。

暴力

别问，问就是只要没超，都可以暴力，更何况是这种时间复杂度O（N）就可以解决的暴力。

因为每一个数字都对应的是它的下标，如果有一个不是，那它就是缺失的数字。

直接看代码：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        for(int i = 0;i<nums.size();i++)
        {
            if(nums[i] != i)
            return i;
        }
        return nums.size();
    }
};

如果一次找完了都没找到 i ，说明缺是就是最后一个元素，最后一个元素就是这个数组的长度。

二分

我们可以通过二分来快速找到这个缺失的位置的附近，然后进行简单的判断来输出返回值。

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)
            right = mid;
            else
            left = mid+1;
        }
        return nums[left]==left?left+1:nums[left]-1;
    }
};

如果这个位置相等，就说明这是缺失数字的左边，如果不相等，说明这是缺失数字的右边。