写点什么

[力扣] 剑指 Offer 第四天 - 0~n-1 中缺失的数字

作者:陈明勇
  • 2022-11-20
    广东
  • 本文字数:843 字

    阅读完需:约 3 分钟

[力扣] 剑指 Offer 第四天 - 0~n-1中缺失的数字

耐心和持久胜过激烈和狂热。

题目来源

来源:力扣(LeetCode)

链接:https://leetcode.cn/problems/que-shi-de-shu-zi-lcof

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题目描述

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

示例

示例 1:


输入: [0,1,3]输出: 2
复制代码


示例 2:


输入: [0,1,2,3,4,5,6,7,9]输出: 8
复制代码

题目分析

  • 根据题意,数组中的元素是有序的,并且在 [0 ~ n - 1] 的区间内只会缺少一个元素,因此,最简单粗暴的方法就是遍历数组,然后判断下标值与元素值是否相等,不相等说明元素丢失,丢失的元素就是下标值。但是最坏情况下,需要遍历整个数组,使用了 O(N) 的时间复杂度。

  • 除了遍历数组以外,因为数组中的元素的有序的,因此可以使用二分法去解题,我们可以观察一下此数组 nums [0,1,2,3,4,5,6,7,9],对于缺失元素的左部分,num[i] = i 是恒成立的,而缺失元素的右部分,num[i] != i,因此可以使用二分法查找右部分的首位元素,下标值就是缺失元素。

算法

  • 获取左边界和右边界 leftright 的值

  • 循环二分

  • 获取中间值 mid = (left + right) / 2

  • 判断下标值是否等于元素,相等则左边界往右移至中间的下一个位置

  • 否则右边界往左移至中间的下一个位置,直至到达缺失元素右部分的首位元素

  • 循环结束后左边界的位置等于缺失元素右部分的首位元素的位置,返回 left 即可

代码实现

func missingNumber(nums []int) int {    left, right := 0, len(nums) - 1    for left <= right {        middle := (left + right) / 2        if nums[middle] == middle {            left = middle + 1        } else {            right = middle -1        }    }    return left}
复制代码

复杂度分析

时间复杂度:O(logN),二分查找法的时间复杂度为 O(logN)。

空间复杂度:O(1),没有使用额外的内存空间。

结尾

如果本文对你有帮助,欢迎点赞收藏加关注,如果本文有错误的地方,欢迎指出!

发布于: 刚刚阅读数: 4
用户头像

陈明勇

关注

一个热爱技术,喜欢专研技术的程序员。 2021-10-20 加入

还未添加个人简介

评论

发布
暂无评论
[力扣] 剑指 Offer 第四天 - 0~n-1中缺失的数字_Go_陈明勇_InfoQ写作社区