JAVA题解 | #寻找第K大# 面试可用

import java.util.*;

public class Solution {
    /**
     * 寻找数组中第K大的元素
     *使用了快速排序的思想，在每一趟排序中，根据枢轴值的位置将数组分为两部分，并递归地在其中一部分中查找第K大的元素。
     * @param a 数组
     * @param n 数组长度
     * @param K 第K大
     * @return 第K大的元素值
     */
    public int findKth(int[] a, int n, int K) {
        // 快速排序，要求时间复杂度 O(nlogn)，空间复杂度 O(1)
        // 向findKth的重载方法中传入第K大元素的索引n-K
        return findKth(a, 0, n - 1, n - K);
    }

    /**
     * 在指定范围内寻找第K大的元素
     *
     * @param a 数组
     * @param low 范围低位索引
     * @param high 范围高位索引
     * @param KIndex 第K大元素的索引
     * @return 第K大的元素值
     */
    public int findKth(int[] a, int low, int high, int KIndex) {
        int pivot = a[low]; // 取待排部分的第一个元素为枢轴值
        int i = low;
        int j = high;

        // 一趟快速排序
        while (i < j) {
            while (a[j] >= pivot && i < j) {
                j--;
            }
            while (a[i] <= pivot && i < j) {
                i++;
            }
            if (i < j) {
                int temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }

        // 将枢轴值放入正确的位置
        a[low] = a[j];
        a[j] = pivot;

        // 根据枢轴位置进行递归查找第K大元素
        if (j == KIndex) {
            return a[j];
        } else if (j > KIndex) {
            return findKth(a, low, j - 1, KIndex);
        } else {
            return findKth(a, j + 1, high, KIndex);
        }
    }
}