在Java中查找第K大元素的几种方法

1. 引言

本文将探讨在唯一数字序列中查找第K大元素的多种解决方案。我们将使用整数数组作为示例，并分析每种算法的平均和最坏时间复杂度。

2. 解决方案

下面介绍三种实现方式：基于排序的简单方案、基于快速选择算法的优化方案及其随机化改进版本。

2.1. 排序法

最直观的思路是直接对数组排序。实现步骤如下：

将数组升序排序
第K大元素位于索引 x = length(array) - k 处

虽然实现简单，但需要完整排序，时间复杂度为 *O(n log n)*：

public int findKthLargestBySorting(Integer[] arr, int k) {
    Arrays.sort(arr);
    int targetIndex = arr.length - k;
    return arr[targetIndex];
}

也可以降序排序后直接取第 k-1 个元素：

public int findKthLargestBySortingDesc(Integer[] arr, int k) {
    Arrays.sort(arr, Collections.reverseOrder());
    return arr[k-1];
}

2.2. 快速选择法

这是对排序法的优化。核心思想是：我们不需要完整排序数组，只需确保第K个元素处于正确位置。

该算法源自快速排序，但通过以下优化减少计算量：

选择基准元素（pivot）并分区
- 通常选择最右侧元素作为基准
- 重排数组：小于基准的元素放左侧，大于基准的放右侧
若基准位置恰好是第K大元素，直接返回
若基准位置大于K，递归处理左子数组；否则处理右子数组

通用实现（可同时查找第K小元素）：

public int 
  findKthElementByQuickSelect(Integer[] arr, int left, int right, int k) {
    if (k >= 0 && k <= right - left + 1) {
        int pos = partition(arr, left, right);
        if (pos - left == k) {
            return arr[pos];
        }
        if (pos - left > k) {
            return findKthElementByQuickSelect(arr, left, pos - 1, k);
        }
        return findKthElementByQuickSelect(arr, pos + 1,
          right, k - pos + left - 1);
    }
    return 0;
}

分区函数实现（基于最右侧基准）：

public int partition(Integer[] arr, int left, int right) {
    int pivot = arr[right];
    Integer[] leftArr;
    Integer[] rightArr;

    leftArr = IntStream.range(left, right)
      .filter(i -> arr[i] < pivot)
      .map(i -> arr[i])
      .boxed()
      .toArray(Integer[]::new);

    rightArr = IntStream.range(left, right)
      .filter(i -> arr[i] > pivot)
      .map(i -> arr[i])
      .boxed()
      .toArray(Integer[]::new);

    int leftArraySize = leftArr.length;
    System.arraycopy(leftArr, 0, arr, left, leftArraySize);
    arr[leftArraySize+left] = pivot;
    System.arraycopy(rightArr, 0, arr, left + leftArraySize + 1,
      rightArr.length);

    return left + leftArraySize;
}

更高效的迭代式分区实现：

public int partitionIterative(Integer[] arr, int left, int right) {
    int pivot = arr[right], i = left;
    for (int j = left; j <= right - 1; j++) {
        if (arr[j] <= pivot) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, right);
    return i;
}

public void swap(Integer[] arr, int n1, int n2) {
    int temp = arr[n2];
    arr[n2] = arr[n1];
    arr[n1] = temp;
}

⚠️ 平均时间复杂度 *O(n)*，但最坏情况（如已排序数组）会退化到 O(n²)

2.3. 随机化快速选择

针对前述方法的改进：随机选择基准元素避免最坏情况。核心改动是：

随机选取一个元素与最右侧元素交换
后续分区逻辑保持不变

实现代码：

public int randomPartition(Integer arr[], int left, int right) {
    int n = right - left + 1;
    int pivot = (int) (Math.random()) * n;
    swap(arr, left + pivot, right);
    return partition(arr, left, right);
}

✅ 实际应用中表现更稳定，期望时间复杂度仍为 O(n)
❌ 最坏时间复杂度仍为 *O(n²)*（但概率极低）

3. 总结

本文讨论了查找第K大元素的三种方案：

方法	平均时间复杂度	最坏时间复杂度	适用场景
排序法	O(n log n)	O(n log n)	简单场景，n较小时
快速选择法	O(n)	O(n²)	大数据量，追求平均性能
随机化快速选择	O(n)	O(n²)	需要避免最坏情况的生产环境

完整实现代码可参考 GitHub仓库。实际开发中，若对性能要求极高，建议优先考虑随机化快速选择法，并注意处理极端输入数据。

Persistence

REST