LeetCode 顺序统计量选择题解

LeetCode 顺序统计量选择题解

题目描述

实现顺序统计量选择算法，在一个整数数组中查找第 k 小的元素。

示例：

输入：[64, 34, 25, 12, 22, 11, 90]，k = 3
输出：22（第 3 小的元素）

解题思路

方法：快速选择算法

思路：

• 快速选择算法的核心思想是基于快速排序的分区操作，通过不断缩小搜索范围来找到第 k 小的元素。
• 具体步骤：
  1. 选择一个基准元素。
  2. 对数组进行分区，将小于基准元素的元素放在左边，大于基准元素的元素放在右边。
  3. 根据基准元素的位置判断第 k 小的元素在哪个分区：
     • 如果基准元素的位置等于 k-1，则基准元素就是第 k 小的元素。
     • 如果基准元素的位置大于 k-1，则第 k 小的元素在左分区。
     • 如果基准元素的位置小于 k-1，则第 k 小的元素在右分区。
  4. 递归地在相应的分区中查找第 k 小的元素。

复杂度分析：

• 时间复杂度：O(n)，其中 n 是数组的长度。平均情况下，每次分区都会将搜索范围减半。
• 空间复杂度：O(log n)，需要额外的空间来存储递归调用的栈。

代码实现

方法：快速选择算法

# 快速选择算法 def quick_select(arr, k): if k < 1 or k > len(arr): return None return quick_select_helper(arr, 0, len(arr) - 1, k - 1) def quick_select_helper(arr, left, right, k): if left == right: return arr[left] # 分区，返回基准元素的位置 pivot_idx = partition(arr, left, right) if pivot_idx == k: return arr[pivot_idx] elif pivot_idx > k: return quick_select_helper(arr, left, pivot_idx - 1, k) else: return quick_select_helper(arr, pivot_idx + 1, right, k) # 分区函数 def partition(arr, left, right): # 选择基准元素（这里选择最后一个元素） pivot = arr[right] i = left - 1 for j in range(left, right): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[right] = arr[right], arr[i + 1] return i + 1 # 测试 def test_quick_select(): arr = [64, 34, 25, 12, 22, 11, 90] print(quick_select(arr.copy(), 1)) # 输出：11 print(quick_select(arr.copy(), 3)) # 输出：22 print(quick_select(arr.copy(), 7)) # 输出：90 if __name__ == "__main__": test_quick_select()

测试用例

测试用例 1：基本情况

输入：[64, 34, 25, 12, 22, 11, 90]，k = 3
输出：22

测试用例 2：k = 1（最小元素）

输入：[64, 34, 25, 12, 22, 11, 90]，k = 1
输出：11

测试用例 3：k = n（最大元素）

输入：[64, 34, 25, 12, 22, 11, 90]，k = 7
输出：90

总结

快速选择算法是一种高效的顺序统计量选择算法，它通过基于快速排序的分区操作来找到第 k 小的元素。快速选择算法的平均时间复杂度为 O(n)，比排序后再选择的方法更高效。

快速选择算法的核心思想是：通过分区操作不断缩小搜索范围，直到找到第 k 小的元素。

掌握快速选择算法的原理和实现，对于理解顺序统计量选择问题非常重要。