使用快速排序Partition算法（分治法O(n)）查找未排序数组缺失值

核心思路 #

因为数组包含1到n里除一个数外的所有数，正常情况下，1到k的数应该正好有k个。我们可以利用快排的Partition函数，把数组分成小于等于基准值和大于基准值的两部分，通过统计左边元素的数量，判断缺失的数在左半区还是右半区，然后递归缩小范围，直到找到缺失的数。

具体步骤 #

1. 实现Partition函数：和快排里的Partition逻辑一致，选一个基准值（比如当前待查找区间的中间值），遍历数组，把小于等于基准的元素移到左边，大于的移到右边，最后返回基准值的最终位置（也就是左边元素的个数）。
2. 递归查找：
   • 确定当前待查找的数值范围[low, high]，初始是[1, n]（n是完整序列的最大值，等于数组长度+1）。
   • 计算中间基准值mid = (low + high) // 2。
   • 用Partition把数组分成<=mid和>mid的两部分，得到左边元素的数量count。
   • 如果count == mid，说明1到mid的数都存在，缺失的数在[mid+1, high]，递归处理这个区间。
   • 如果count < mid，说明缺失的数在[low, mid]，递归处理这个区间。
   • 当low == high时，这个值就是缺失的数。

代码示例（Python） #

def partition(arr, pivot):
    left = 0
    right = len(arr) - 1
    while left <= right:
        # 找左边大于pivot的元素
        while left <= right and arr[left] <= pivot:
            left += 1
        # 找右边小于等于pivot的元素
        while left <= right and arr[right] > pivot:
            right -= 1
        if left < right:
            arr[left], arr[right] = arr[right], arr[left]
    # left的位置就是<=pivot的元素个数
    return left

def find_missing_recursive(arr, low, high):
    if low == high:
        return low
    mid = (low + high) // 2
    count = partition(arr, mid)
    if count == mid:
        return find_missing_recursive(arr, mid+1, high)
    else:
        return find_missing_recursive(arr, low, mid)

# 测试示例
test_arr = [8,1,5,4,2,7,6]
n = len(test_arr) + 1
print(find_missing_recursive(test_arr, 1, n))  # 输出3

额外说明 #

• 如果不想修改原数组，可以在调用Partition时传入数组的副本（比如partition(arr.copy(), mid)），但会牺牲一点效率。
• 可以给Partition函数增加随机选基准的逻辑，避免最坏情况下O(n²)的时间复杂度，让平均复杂度稳定在O(n log n)。

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