[!info] related notes 算法面试题型 MOC 快速排序

随机选择（Randomized Select）

目标：在无序数组中找第 K 小（或第 K 大）。

思想

随机选 pivot 做一次 partition 后：

• 如果目标下标落在 “< pivot” 区间，继续在左边找。
• 如果落在 “> pivot” 区间，继续在右边找。
• 如果落在 “== pivot” 区间，答案就是 pivot。

每次都能丢掉一大块不可能的元素，期望时间复杂度 $O(n)$。

实现要点

• 用三路划分（<, ==, >）更稳，重复元素多时优势明显。
• 第 K 大可以转换成第 (n-k) 小。

Java Template (Iterative)

import java.util.*;

public class RandomizedSelect {
    static int findKthLargest(int[] nums, int k) {
        // kth largest => index (n - k) in sorted order (0-indexed)
        return select(nums, nums.length - k);
    }

    static int select(int[] arr, int index) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int pivot = arr[l + (int) (Math.random() * (r - l + 1))];
            int[] range = partition(arr, l, r, pivot);
            if (index < range[0]) {
                r = range[0] - 1;
            } else if (index > range[1]) {
                l = range[1] + 1;
            } else {
                return arr[index];
            }
        }
        throw new IllegalArgumentException("index out of range");
    }

    static int[] partition(int[] arr, int l, int r, int pivot) {
        int less = l - 1;
        int more = r + 1;
        int i = l;
        while (i < more) {
            if (arr[i] < pivot) swap(arr, ++less, i++);
            else if (arr[i] > pivot) swap(arr, i, --more);
            else i++;
        }
        return new int[] { less + 1, more - 1 };
    }

    static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}