java查找一个数组的第K大的数

在Java中，可以使用多种算法来找到数组中的第k大的元素，这里提供一种基于快速选择（QuickSelect）的解决方案，它是一种改进版的快速排序算法，适用于解决“找出第k大/小元素”的问题，而不是完全排序整个数组：

public class KthLargest {
    public static int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k < 1 || k > nums.length) {
            throw new IllegalArgumentException("Invalid input");
        }
        
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private static int partition(int[] nums, int left, int right, int pivotIndex) {
        int pivotValue = nums[pivotIndex];
        swap(nums, pivotIndex, right); // 将pivot放在末尾
        int storeIndex = left;

        for (int i = left; i < right; i++) {
            if (nums[i] > pivotValue) {
                swap(nums, i, storeIndex);
                storeIndex++;
            }
        }
        swap(nums, storeIndex, right); // 将pivot放回正确的位置
        return storeIndex;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private static int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) { // 基线条件：只有一个元素，直接返回
            return nums[left];
        }

        int pivotIndex = partition(nums, left, right, (left + right) / 2); // 随机选取pivot

        if (k == pivotIndex) {
            return nums[k]; // 找到的就是pivot
        } else if (k < pivotIndex) {
            // k小于pivot，继续在左半部分查找
            return quickSelect(nums, left, pivotIndex - 1, k);
        } else {
            // k大于pivot，继续在右半部分查找
            return quickSelect(nums, pivotIndex + 1, right, k);
        }
    }