如何在含重复元素的百万级有序数组中查找缺失数字？

针对升序排列、存在重复和缺失的百万级数字序列，以下是几种高效的解决方案，避免低效的全量循环：

方案一：前缀唯一计数+二分查找 #

利用升序数组的连续重复特性，先快速统计前缀唯一元素数量，再通过二分定位缺失位置：

1. 预处理生成前缀唯一计数数组：
   遍历一次数组，记录每个位置前的唯一元素总数（相同元素连续，只需对比当前与前一个元素即可），时间复杂度O(n)：

   def get_prefix_unique(nums):
       if not nums:
           return []
       prefix = [1] * len(nums)
       for i in range(1, len(nums)):
           prefix[i] = prefix[i-1] + (0 if nums[i] == nums[i-1] else 1)
       return prefix
   

2. 二分查找缺失数字：
   已知完整序列的起始值first，通过二分找到第一个位置mid，使得nums[mid] > first + prefix[mid] - 1，此时first + prefix[mid] - 1就是缺失的数字，时间复杂度O(logn)。

   示例：数组[1,1,2,4]，first=1，前缀数组为[1,1,2,3]。当mid=3时，nums[3]=4 > 1+3-1=3，因此缺失数字为3。

方案二：跳过重复的优化二分查找 #

无需预处理，直接在二分过程中跳过连续重复元素，复用无重复场景的核心逻辑：

1. 初始化二分指针left=0，right=len(nums)-1，已知完整序列起始值first。
2. 循环查找：
   • 找到当前中间位置mid对应的第一个不重复的左边界（向左跳过所有与nums[mid]相同的元素）。
   • 找到当前中间位置mid对应的最后一个不重复的右边界（向右跳过所有与nums[mid]相同的元素）。
   • 计算nums[mid]在无缺失无重复序列中应处的索引：expected_idx = nums[mid] - first。
   • 若左边界left_mid > expected_idx：缺失在左半区间，调整right = left_mid - 1。
   • 若右边界right_mid < expected_idx：缺失在右半区间，调整left = right_mid + 1。
   • 否则：当前元素区间位置正确，调整left = right_mid + 1。
3. 循环结束后，缺失数字为first + left。

该方案全程O(logn)时间复杂度，适合超大规模数据。

方案三：多缺失场景的滑动窗口法 #

如果需要找出所有缺失数字，可采用滑动窗口：

1. 初始化窗口左指针left=0，已知完整序列起始值first。
2. 遍历数组，每次将右指针right移动到当前元素的最后一个重复位置。
3. 计算当前窗口内唯一元素对应的理论范围：current_start = nums[left]，current_end = nums[right]。
4. 对比理论范围应包含的元素数（current_end - current_start +1）与实际唯一元素数（1，因为窗口内是重复元素），找出中间缺失的数字。
5. 移动左指针到right+1，重复上述步骤，直到遍历结束。
6. 最后检查序列结束值last，若数组最后一个元素小于last，补充剩余缺失数字。

内容的提问来源于stack exchange，提问作者Sambhav Khandelwal