寻找数组中第K个最大元素

Problem

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2 Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4

Idea

Solution 1: Heap

Use a min-heap of size k. The idea is to keep only the k largest elements seen so far. Process each number in the array: 1. Add the number to the min-heap. 2. If the heap size becomes larger than k, remove the smallest element. 3. After processing all numbers, the heap contains the k largest elements. 4. The smallest element in that heap is therefore the kth largest element overall.

Time complexity:\(O(n\log k)\), Space complexity: \(O(k)\)

Solution 2: Quickselect

The k-th largest element is at index n - k if the array were sorted in ascending order. Instead of sorting the whole array, Quickselect chooses a pivot and partitions the array so that smaller elements are on the left and larger elements are on the right. After partitioning, the pivot is in its correct final position. Compare that position with n - k: - If they are equal, the pivot is the answer. - If the pivot is to the left of the target, continue searching only the right part. - If the pivot is to the right of the target, continue searching only the left part.

Repeat until the target position is found. Quickselect modifies the array in place and has \(O(n)\) average time complexity and \(O(1)\) extra space with an iterative implementation.

Pseudo-code

Solution 1: Heap

minHeap = empty heap;

for (each value in array) {
    insert value into minHeap;

    if (minHeap.size() > k) {
        remove smallest value from minHeap;
    }
}

return smallest value in minHeap;

Solution 2: Quickselect

target = length(array) - k;

return QuickSelect(array, 0, length(array) - 1, target);


QuickSelect(array, left, right, target) {
    pivotPosition = Partition(array, left, right);

    if (pivotPosition == target) {
        return array[pivotPosition];
    } 
    else if (pivotPosition < target) {
        return QuickSelect(array, pivotPosition + 1, right, target);
    } 
    else {
        return QuickSelect(array, left, pivotPosition - 1, target);
    }
}