215. 数组中的第K个最大元素 - 力扣（LeetCode） (opens new window)

暴力

时间：O(N logN)，Java的Arrays.sort()底层采用双基准快排优

空间：O(1)

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

快速选择

时间：平均O(N)，最坏O(N²)（可通过随机化基准值优化）

空间：O(logN)（递归栈开销）

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

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);
    }
}

// 随机化基准的分区函数（Lomuto方案）
private int partition(int[] nums, int left, int right) {
    int randomIndex = left + (int)(Math.random() * (right - left + 1));
    swap(nums, randomIndex, right);
    int pivot = nums[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            i++;
            swap(nums, i, j);
        }
    }
    swap(nums, i + 1, right);
    return i + 1;
}

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

堆排序（优先队列）

时间：O(N logk)，每次插入/弹出堆顶的时间为O(logk)

空间：O(k)

// 使用PriorityQueue（默认小顶堆）
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int num : nums) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    // pq 中剩下的是 nums 中 k 个最⼤元素，
    // 堆顶是最⼩的那个，即第 k 个最⼤元素
    return heap.peek();
}

原地堆排序优化

时间：O(N logk)，但常数更优（省去PriorityQueue的封装开销）

空间：O(1)

public int findKthLargest(int[] nums, int k) {
    // 构建初始小顶堆（前k个元素）
    for (int i = (k - 2) / 2; i >= 0; i--) {
        heapify(nums, i, k);
    }
    // 遍历剩余元素并调整堆
    for (int i = k; i < nums.length; i++) {
        if (nums[i] > nums[0]) {
            swap(nums, 0, i);
            heapify(nums, 0, k);
        }
    }
    return nums[0];
}

private void heapify(int[] nums, int parent, int heapSize) {
    int left = 2 * parent + 1;
    while (left < heapSize) {
        int minChild = (left + 1 < heapSize && nums[left] > nums[left + 1]) ? left + 1 : left;
        if (nums[parent] <= nums[minChild]) break;
        swap(nums, parent, minChild);
        parent = minChild;
        left = 2 * parent + 1;
    }
}

计数排序

时间：O(N + M)，M为数值范围（本题M=2e4）

空间：O(M)

public int findKthLargest(int[] nums, int k) {
    int[] count = new int[20001];
    for (int num : nums) {
        count[num + 10000]++; // 处理负数
    }
    int sum = 0;
    for (int i = count.length - 1; i >= 0; i--) {
        sum += count[i];
        if (sum >= k) {
            return i - 10000;
        }
    }
    return -1;
}