class Solution {// 寻找数组中第k大的元素public int findKthLargest(int[] nums, int k) {// 初始化堆的大小为数组长度int heapSize = nums.length;// 构建最大堆buildMaxHeap(nums, heapSize);// 从最后一个元素开始，逐个将堆顶元素（最大值）与当前元素交换，然后重新调整堆for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {swap(nums, 0, i); // 交换堆顶元素与当前元素--heapSize; // 减小堆的大小maxHeapify(nums, 0, heapSize); // 重新调整堆}return nums[0]; // 返回堆顶元素，即第k大的元素}// 构建最大堆public void buildMaxHeap(int[] a, int heapSize) {// 从最后一个非叶子节点开始向上调整堆for (int i = heapSize / 2; i >= 0; --i) {maxHeapify(a, i, heapSize);}}// 调整堆，使其满足最大堆的性质public void maxHeapify(int[] a, int i, int heapSize) {// 计算左右子节点的索引int l = i * 2 + 1, r = i * 2 + 2, largest = i;// 如果左子节点存在且大于当前节点，则更新最大节点索引if (l < heapSize && a[l] > a[largest]) {largest = l;}// 如果右子节点存在且大于当前最大节点，则更新最大节点索引if (r < heapSize && a[r] > a[largest]) {largest = r;}// 如果最大节点不是当前节点，交换它们并继续调整堆if (largest != i) {swap(a, i, largest);maxHeapify(a, largest, heapSize);}}// 交换数组中的两个元素public void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}
}
public class Solution {// 快速选择算法，用于查找第 k 大的元素private int quickSelect(List<Integer> nums, int k) {// 随机选择基准数Random rand = new Random();int pivot = nums.get(rand.nextInt(nums.size()));// 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中List<Integer> big = new ArrayList<>();List<Integer> equal = new ArrayList<>();List<Integer> small = new ArrayList<>();for (int num : nums) {if (num > pivot)big.add(num); // 大于基准数的元素放入 big 列表else if (num < pivot)small.add(num); // 小于基准数的元素放入 small 列表elseequal.add(num); // 等于基准数的元素放入 equal 列表}// 第 k 大元素在 big 中，递归划分if (k <= big.size())return quickSelect(big, k);// 第 k 大元素在 small 中，递归划分if (nums.size() - small.size() < k)return quickSelect(small, k - nums.size() + small.size());// 第 k 大元素在 equal 中，直接返回 pivotreturn pivot;}// 主函数，用于调用快速选择算法public int findKthLargest(int[] nums, int k) {List<Integer> numList = new ArrayList<>();for (int num : nums) {numList.add(num); // 将数组转换为列表}return quickSelect(numList, k); // 调用快速选择算法查找第 k 大的元素}
}