首页 > 编程语言 > 详细

找出有序数组中缺失的数字

时间:2020-06-18 22:42:43      阅读:49      评论:0      收藏:0      [点我收藏+]

思路描述:假设 0~n-1 中没有数字 i ,那么这 n - 1 个数字的和为 sum = n*(n-1)/2 - i,那么 i = n*(n-1)/2 - sum。


技术分享图片

 

 


其实我们可以注意到,从缺失的数字 i 开始下标和数值不相等


技术分享图片

 

 


前两种做法时间复杂度均为 O(n),有没有更优的做法?由第二种做法我们知道,如果 k == nums[k],那么缺失的数字一定在 k 右边,如果 k != nums[k],那么缺失的数字要么为 k 要么在 k 左边;这个很类似于二分查找,我们也可以使用二分的思想去优化时间复杂度。


技术分享图片

 

 

作者:yizhe-shi
链接:https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/solution/c-onolgnfang-fa-jie-da-by-yizhe-shi/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

找出有序数组中缺失的数字

原文:https://www.cnblogs.com/sweet-li/p/13160436.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!