Leetcode 剑指 Offer 53 - II. 0~n-1中缺失的数字
程序员文章站
2024-03-07 21:33:03
...
一、题目
题目描述:
二、思路
给定一个排序的数组,因此直接应用二分的思想;题目中限制了所有的数字均为0~n-1之内且不重复,通过观察可以发现,只要其中间元素的索引等于其值,则缺失数字必定在右半区间。因为只要你前面缺了任何一个数,必然会导致后面的数都依次左移一位,所以有:
- 当mid ==nums[mid] 时,有left = mid + 1;
- 当mid !=nums[mid] 时, 有right = mid - 1
当left>right时则跳出循环,此时left记录着那个缺失的元素,直接返回left即可。
三、代码
class Solution:
def missingNumber(self, nums: List[int]) -> int:
left, right = 0, len(nums)-1
mid = (left + right) // 2
while left <= right:
if nums[mid] == mid: left = mid + 1
else: right = mid - 1
mid = (left + right) // 2
return left
四、复杂度分析
- 时间复杂度为:O(logN)
- 空间复杂度为:O(1)
推荐阅读
-
Leetcode 剑指 Offer 53 - II. 0~n-1中缺失的数字
-
剑指offer【53】:0~n-1数组缺失值
-
【剑指 Offer 53 - II】0~n-1中缺失的数字
-
剑指offer书(53)-2:0-n-1中缺失的数字
-
剑指OFFER----53-2、0~n-1中缺失的数字(js实现)
-
剑指 Offer 53 - II. 0~n-1中缺失的数字
-
剑指offer 53 - II. 0~n-1中缺失的数字
-
剑指 Offer 53 - II. 0~n-1中缺失的数字
-
Leetcode——剑指offer面试题03. 数组中重复的数字
-
python--剑指offer--中等--56 - II. 数组中数字出现的次数 II