510 字
3 分钟
【算法笔记】（七）随机选择算法
随机选择算法（Randomized Select / Quickselect）
题目描述
在无序数组中寻找第 K 大的数。
给定整数数组 nums 和整数 k，请返回数组中第 k 大的元素。
请注意：你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
要求
- 时间复杂度：
O(n)（期望） - 额外空间复杂度：
O(1)
思路说明
第 K 大等价于：把数组按从小到大排序后，找到下标为 n - K 的元素（0-based）。
例如：
- 数组长度为
n - 第
K大元素 = 排序后位置n - K的元素
因此可以将问题转换为：在数组中寻找“第 (n - K) 小（按下标）”的元素，用随机选择（Quickselect）实现，期望 O(n)。
Java 实现代码
package org.example;
public class Main {
static int[] arr = {0, 1, 2, 3, 4, 5, 6, 7};
public static void main(String[] args) { int K = 5;
// 将问题转换：求第K大的数 = 求排序后下标为 arr.length - K 的数 int i = randomizedSelect(arr.length - K);
System.out.println(i); }
// 如果 arr 排序后，第 k 位置（0-based）的数是什么 public static int randomizedSelect(int k) { int ans = 0;
for (int l = 0, r = arr.length - 1; l <= r; ) { // 在 [l, r] 随机选一个 pivot 值 x int x = arr[l + (int) (Math.random() * (r - l + 1))];
// 三路划分：<x | ==x | >x partition(l, r, x);
// 根据 x 所在区间与 k 的关系，缩小搜索范围 if (first > k) r = first - 1; else if (last < k) l = last + 1; else { ans = x; break; } }
return ans; }
static int first; static int last;
// 已知数组在 [l, r] 范围内一定有值 x // 划分数组：<x 的放左边，==x 的放中间，>x 的放右边 // 更新全局变量 first、last 为 ==x 的左右边界 private static void partition(int l, int r, int x) { first = l; last = r; int i = l;
while (i <= last) { if (arr[i] == x) i++; else if (arr[i] < x) swap(first++, i++); else swap(i, last--); } }
private static void swap(int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }}部分信息可能已经过时