[力扣] 剑指 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:
示例 2:
题目分析
根据题意,数组中的元素是有序的,并且在
[0 ~ n - 1]
的区间内只会缺少一个元素,因此,最简单粗暴的方法就是遍历数组,然后判断下标值与元素值是否相等,不相等说明元素丢失,丢失的元素就是下标值。但是最坏情况下,需要遍历整个数组,使用了 O(N) 的时间复杂度。除了遍历数组以外,因为数组中的元素的有序的,因此可以使用二分法去解题,我们可以观察一下此数组 nums
[0,1,2,3,4,5,6,7,9]
,对于缺失元素的左部分,num[i] = i 是恒成立的,而缺失元素的右部分,num[i] != i,因此可以使用二分法查找右部分的首位元素,下标值就是缺失元素。
算法
获取左边界和右边界
left
和right
的值循环二分
获取中间值
mid = (left + right) / 2
判断下标值是否等于元素,相等则左边界往右移至中间的下一个位置
否则右边界往左移至中间的下一个位置,直至到达缺失元素右部分的首位元素
循环结束后左边界的位置等于缺失元素右部分的首位元素的位置,返回
left
即可
代码实现
复杂度分析
时间复杂度:O(logN),二分查找法的时间复杂度为 O(logN)。
空间复杂度:O(1),没有使用额外的内存空间。
结尾
如果本文对你有帮助,欢迎点赞收藏加关注,如果本文有错误的地方,欢迎指出!
版权声明: 本文为 InfoQ 作者【陈明勇】的原创文章。
原文链接:【http://xie.infoq.cn/article/d35274718c96fc5745f220855】。文章转载请联系作者。
评论