难度: Medium
Submission
运行时间: 25 ms
内存: 20.8 MB
# class Solution:
# def missingElement(self, nums: List[int], k: int) -> int:
# for i in range(len(nums)):
# if i + 1 < len(nums):
# if nums[i+1] - nums[i] >= k + 1:
# return nums[i] + k
# else:
# k = k - (nums[i+1] - nums[i]) + 1
# return nums[-1] + k
class Solution:
def missingElement(self, nums: List[int], k: int) -> int:
def compute_blank(l, r, nums): # 计算当前范围的数组中有几个空位
return nums[r] - nums[l] - (r - l)
n_lost = compute_blank(0, len(nums)-1, nums)
if k > n_lost:
return nums[-1] + k - n_lost
l = 0
r = len(nums) - 1
while l < r - 1: # 两指针相邻时跳出循环
mid = int((l + r)/2)
n_lost_left = compute_blank(l, mid, nums)
if n_lost_left >= k: # 若左侧数组的空位大于k，说明缺失数在左边，更新右边界
r = mid
else: # 否则选取右侧数组，并且更新k，因为左侧数组会含有一定数量的空位
l = mid
k -= n_lost_left
return nums[l] + k
Explain
此题解利用二分搜索的方法来寻找有序数组中的缺失元素。首先定义一个函数 `compute_blank`，用于计算给定两个索引之间的空位数量。然后检查若给定的 k 大于数组中总的缺失数，则直接在数组的最后一个数后面加上相应的数量。如果不是，则使用二分搜索，通过不断调整左右边界，缩小可能存在缺失元素的范围，直到找到确切的缺失元素位置。
时间复杂度: O(log n)
空间复杂度: O(1)
# class Solution:
# def missingElement(self, nums: List[int], k: int) -> int:
# for i in range(len(nums)):
# if i + 1 < len(nums):
# if nums[i+1] - nums[i] >= k + 1:
# return nums[i] + k
# else:
# k = k - (nums[i+1] - nums[i]) + 1
# return nums[-1] + k
class Solution:
def missingElement(self, nums: List[int], k: int) -> int:
def compute_blank(l, r, nums): # 计算当前范围的数组中有几个空位
return nums[r] - nums[l] - (r - l)
n_lost = compute_blank(0, len(nums)-1, nums)
if k > n_lost:
return nums[-1] + k - n_lost
l = 0
r = len(nums) - 1
while l < r - 1: # 两指针相邻时跳出循环
mid = int((l + r)/2)
n_lost_left = compute_blank(l, mid, nums)
if n_lost_left >= k: # 若左侧数组的空位大于k，说明缺失数在左边，更新右边界
r = mid
else: # 否则选取右侧数组，并且更新k，因为左侧数组会含有一定数量的空位
l = mid
k -= n_lost_left
return nums[l] + k
Explore
函数`compute_blank`用于计算在有序数组中两个给定索引`l`和`r`之间的缺失元素数量。具体的计算公式是`nums[r] - nums[l] - (r - l)`。这个公式的意思是：从`nums[l]`到`nums[r]`之间理论上应该有`nums[r] - nums[l] + 1`个整数（包括`nums[l]`和`nums[r]`），但数组中实际上只有`r - l + 1`个元素，因此缺失的元素数量就是`nums[r] - nums[l] - (r - l)`。
在这个二分搜索算法中，使用`l < r - 1`是为了避免在更新左右界时造成无限循环。当`l`和`r`相邻时，即`l + 1 == r`，如果使用`l <= r`作为循环条件，可能导致`mid`一直等于`l`，从而使得`l`或`r`的更新停滞不前。设置`l < r - 1`确保了循环能够在两指针相邻时退出，这时候下一个缺失的元素一定位于`nums[l]`和`nums[r]`之间。
在二分搜索过程中，如果发现左边子数组中的缺失元素数量`n_lost_left`小于或等于`k`，表明所求的第`k`个缺失元素不在左边子数组中。因此，需要将搜索范围缩小到右边子数组，并且更新`k`的值为`k - n_lost_left`，即减去左边已经计算过的缺失元素数量。这样的操作确保了`k`始终表示在当前考虑的数组片段中所要找的缺失元素的序号。
如果`k`大于数组中所有缺失的元素数量`n_lost`，这意味着即使将数组中现有的所有缺失元素全部计算完，仍然不能满足找到第`k`个缺失元素的要求。因此，需要在数组的最后一个元素`nums[-1]`之后继续寻找缺失的元素。`nums[-1] + k - n_lost`的计算基于这样的逻辑：从数组最后一个元素`nums[-1]`起，再向上增加`k - n_lost`个单位，即可达到第`k`个缺失元素的值。