跟着姚桑学算法-0到n-1中缺失的数字

简介: 剑指offer算法

题. 0到n-1中缺失的数字

一个长度为 n−1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 到 n−1 之内。

在范围 0 到 n−1 的 n 个数字中有且只有一个数字不在该数组中,请找出这个数字。

数据范围
1≤n≤1000

样例

输入:[0,1,2,4]

输出:3

【题解】--- 二分法

这道题目给定的是递增数组,假设数组中第一个缺失的数是 x,那么数组中的数如下所示;
在这里插入图片描述
在这里插入图片描述
从中可以看出,数组左边蓝色部分都满足 nums[i] == i

数组右边x-1后的部分都不满足 nums[i] == i,因此我们可以二分出分界点 x 的值。

另外要注意特殊情况:当所有数都满足nums[i] == i 时,表示缺失的是 n。

复杂度分析:

二分中的迭代只会执行 O(logn) 次,因此时间复杂度是 O(logn)。

C++代码实现:

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if (nums.empty()) return 0;

        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] != mid) r = mid;
            else l = mid + 1;
        }

        if (nums[r] == r) r ++ ;
        return r;
    }
};
目录
相关文章
|
6月前
|
算法 C语言
C语言----判断n是否是2的次方数,利用到按位与&,算法n&(n-1)
C语言----判断n是否是2的次方数,利用到按位与&,算法n&(n-1)
算法练习第九天——只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
|
算法 C语言
C语言:使用 普通方法 和 二分查找算法(折半查找算法) 在一个有序数组中查找具体的某个数字n-1
思路一:普通方法 (逻辑简单,在无序数组中也可以使用,但效率较低,需要逐个查找) 总体思路:
102 0
|
算法 索引
算法创作 | 0到n-1中缺失的数字问题解决方法
算法创作 | 0到n-1中缺失的数字问题解决方法
100 0
|
机器学习/深度学习 算法 数据可视化
在python中使用KNN算法处理缺失的数据
在python中使用KNN算法处理缺失的数据
320 1
在python中使用KNN算法处理缺失的数据
|
机器学习/深度学习 存储 算法
算法打卡Day23_leetcode _136. 只出现一次的数字
算法打卡Day23_leetcode _136. 只出现一次的数字
算法打卡Day23_leetcode _136. 只出现一次的数字
|
JavaScript 算法 前端开发
【前端算法】JS实现数字千分位格式化
JS实现数字千分位格式化的几种思路,以及它们之间的性能比较
350 1
|
机器学习/深度学习 算法 数据建模
K近邻算法识别数字---OpenCV-Python开发指南(40)
K近邻算法识别数字---OpenCV-Python开发指南(40)
176 0
K近邻算法识别数字---OpenCV-Python开发指南(40)
|
存储 算法 Java
算法打卡Day5_lecode_448. 找到所有数组中消失的数字
算法打卡Day5_lecode_448. 找到所有数组中消失的数字
算法打卡Day5_lecode_448. 找到所有数组中消失的数字
|
算法 Java
Map与Set高频面试算法题(只出现一次的数字,复制带随机指针的链表,宝石与石头,旧键盘,前k个高频单词)(Java实现)
给一个非空整数数组,只有一个元素出现了一次,剩余的元素都出现了两次,,请找出那个只出现一次的数字
Map与Set高频面试算法题(只出现一次的数字,复制带随机指针的链表,宝石与石头,旧键盘,前k个高频单词)(Java实现)