力扣鏈接

題意

給定整數數組 nums 和整數 k，請返回數組中第 k 個最大的元素。

請注意，你需要找的是數組排序後的第 k 個最大的元素，而不是第 k 個不同的元素。

你必須設計並實現時間複雜度為 O(n) 的算法解決此問題。

示例 1:

輸入: [3,2,1,5,6,4], k = 2
輸出: 5

示例 2:

輸入: [3,2,3,1,2,4,5,5,6], k = 4
輸出: 4

提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

思路及解答

堆排序

這道題就是經典的 topK 問題， 實現一個小根堆，規定堆的元素大小是 k 個，將比堆頂大的元素進堆。最後遍歷完數組之後，此時堆頂是 k 個元素中最小的，有就是所有元素中第 k 大的了。

可以用PriorityQueue的最小堆來實現：

public class KthLargestMinHeap {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        
        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }
        return minHeap.peek();
    }
}

升序排序後索引為 len - k 的元素

其實題目已經告訴我們了：

你需要找的是數組排序後的第 k 個最大的元素，而不是第 k 個不同的元素。

因此，升序排序以後，返回索引為 len - k 這個元素即可。

代碼如下：

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

• 時間複雜度：_O(NlogN)_。這裏 N 是數組的長度，算法的性能消耗主要在排序，JDK 默認使用快速排序，因此時間複雜度為O(NlogN)。
• 空間複雜度：O(1)。這裏是原地排序，沒有藉助額外的輔助空間。

但是，如果出了這道題，顯然不是想讓你調 API ，而是看你對快排的理解

藉助快排 partition 操作定位（推薦）

“快速排序” 中的 partition(切分)操作簡單介紹如下：

• 對於某個索引i，nums[i] 已經排序完，即 nums[i] 經過 partition(切分)操作以後會放置在它 “最終應該放置的地方”；
• nums[left] 到 nums[i - 1] 中的所有元素都不大於 nums[i]；
• nums[i + 1] 到 nums[right] 中的所有元素都不小於 nums[i]。

很顯然，nums[i] 最終所在的位置，也就是它排序後的具體位置。也就是説，如果實現的排序是降序排序，那麼第k個位置的數據，也確定就是第k大的

而這樣每經過一次 partition操作就能縮小搜索的範圍，這樣的思想叫做 “減而治之”(是 “分而治之” 思想的特例)。下面是參考代碼：

public class Solution {
 
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
 
        // 轉換一下，第 k 大元素的索引是 len - k
        int target = len - k;
 
        while (true) {
            int index = partition(nums, left, right);
            if (index == target) {
                return nums[index];
            } else if (index < target) {
                left = index + 1;
            } else {
                right = index - 1;
            }
        }
    }
 
    public static int partition(int[] array, int low, int high) {
        // 取最後一個元素作為中心元素
        int pivot = array[high];
        // 定義指向比中心元素大的指針，首先指向第一個元素
        int pointer = low;
        // 遍歷數組中的所有元素，將比中心元素大的放在右邊，比中心元素小的放在左邊
        for (int i = low; i < high; i++) {
            if (array[i] <= pivot) {
                // 將比中心元素小的元素和指針指向的元素交換位置 
                // 如果第一個元素比中心元素小，這裏就是自己和自己交換位置，指針和索引都向下一位移動 
                // 如果元素比中心元素大，索引向下移動，指針指向這個較大的元素，直到找到比中心元素小的元素，並交換位置，指針向下移動
                swap(array, i, pointer);
                pointer++;
            }
        }
        // 將中心元素和指針指向的元素交換位置
        swap(array, pointer, high);
        return pointer;
    }
    
    private static void swap(int[] arr, int i, int j) { 
        int temp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = temp; 
    }
}

• 時間複雜度：O(N)。這裏 N 是數組的長度。
• 空間複雜度：O(1)。切分過程可以不借助額外的數組空間，僅通過交換數組元素實現，沒有藉助額外的輔助空間。