import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 读取k值
        int k = scanner.nextInt();

        Solution solution = new Solution();
        int result = solution.findKthLargest(nums, k);

        // 输出结果
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int num : nums) {
            queue.add(num);
            // 堆大小超过k时，弹出最小元素
            if (queue.size() > k) {
                queue.poll();
            }
        }
        // 堆顶即为第k大元素
        return queue.peek();
    }
}

🚀 解法2：快速选择法（满足O(n)要求）

🔍 思路解析

核心策略：基于快速排序的分区思想，每次选择一个“基准元素”，将数组分成“比基准大”“等于基准”“比基准小”的三部分，通过判断基准的位置，缩小查找范围，直到找到第 k 大的元素。

定义分区函数：随机选基准，将数组中比基准大的元素放左边，比基准小的放右边；
递归/迭代调整查找范围：
- 若基准的位置 == k-1（数组从0开始，第k大对应下标k-1），直接返回基准；
- 若基准位置 < k-1，在右侧继续查找；
- 若基准位置 > k-1，在左侧继续查找。

✅ 快速选择代码（Java）

import java.util.Random;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 读取k值
        int k = scanner.nextInt();

        Solution solution = new Solution();
        int result = solution.findKthLargest(nums, k);

        // 输出结果
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    private Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k - 1);
    }

    // 在[left, right]范围内找下标为target的元素
    private int quickSelect(int[] nums, int left, int right, int target) {
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == target) {
            return nums[pivotIndex];
        } else if (pivotIndex < target) {
            return quickSelect(nums, pivotIndex + 1, right, target);
        } else {
            return quickSelect(nums, left, pivotIndex - 1, target);
        }
    }

    // 分区：返回基准最终的下标，保证左边≥基准，右边≤基准
    private int partition(int[] nums, int left, int right) {
        // 随机选基准，避免最坏情况
        int randomIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, randomIndex);

        int pivot = nums[left];
        int i = left, j = right;
        while (i < j) {
            // 从右找比基准大的元素
            while (i < j && nums[j] <= pivot) j--;
            // 从左找比基准小的元素
            while (i < j && nums[i] >= pivot) i++;
            swap(nums, i, j);
        }
        // 基准放到最终位置
        swap(nums, left, i);
        return i;
    }

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