原文題目

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?

題目摘要

1. 題目描述：給定一個整數陣列 nums 和一個整數 k，回傳陣列中第 k 大的元素。注意，這裡的第 k 大指的是排序後的第 k 大，而不是第 k 個不同的元素。
2. 輸入：整數陣列 nums、整數 k。
3. 輸出：回傳陣列中第 k 大的元素。

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

解題思路一

1. 選擇算法（Quick Select）：
   • 選擇樞紐：首先從陣列中選擇一個樞紐元素，這裡選擇的是陣列的最後一個元素。
   • 分區：將陣列分為兩部分，一部分比樞紐元素大，一部分比樞紐元素小。
   • 遞迴：根據第 k 大元素應該在左邊還是右邊的分區，進一步對該分區進行遞迴，直到找到第 k 大的元素。
2. 計算位置：
   • 每次分區後，樞紐元素會被放置在其最終的位置上，通過計算這個位置來判斷第 k 大的元素在哪一側的分區。

程式碼一

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        //透過快速選擇找到第 n-k+1 小的元素
        int p = quickSelect(nums, 0, n-1, n-k+1);
        return nums[p]; //回傳該位置的元素即為第 k 大的元素
    }
    private int quickSelect(int[] nums, int low, int high, int k) {
        //選擇樞紐元素，這裡選擇陣列的最後一個元素作為樞紐
        int pivot = nums[high];
        int i = low, j = high;
        //開始進行分區操作，確保左邊的元素都大於樞紐
        while (i < j) {
            //如果當前元素大於樞紐，將該元素與右邊的較大元素交換位置
            if (nums[i++] > pivot) swap(nums, --i, --j);
        }
        //將樞紐放到正確的位置上
        swap(nums, i, high);
        //計算樞紐左邊有多少個元素
        int m = i - low + 1;
        //如果 m 等於 k，說明當前的 i 位置就是第 k 小的元素
        if (m == k) return i;
        //如果 m 大於 k，則第 k 小的元素在左邊，繼續在左邊進行快速選擇
        else if (m > k) return quickSelect(nums, low, i - 1, k);
        //如果 m 小於 k，則第 k 小的元素在右邊，遞迴查找右半部分
        else return quickSelect(nums, i + 1, high, k - m);
    }
    //用來交換陣列中的兩個元素
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

• 注意： 程式碼一在leetcode中提交會出現Time Limit Exceeded的提示，這是因為此解法在某些情況下quickSelect 的效率不高，超過了時間限制。

解題思路二

1. minHeap的使用：
   • 我們建立了一個最小堆（PriorityQueue），用來儲存當前遇到的前 k 大的元素。
   • minHeap是一種特殊的二元樹結構，根節點是最小的元素。這使得我們可以在不排序整個陣列的情況下有效地跟踪前 k 大的元素。
2. 遍歷數組：
   • 我們逐個遍歷數組中的每個元素，並將每個元素加入minHeap。
   • 每次加入一個新元素之後，檢查heap的大小是否超過 k。如果超過 k，我們就移除heap頂（最小的元素），從而保證heap中始終只保存前 k 大的元素。
3. 保持前 k 大的元素：
   • 當遍歷完成時，heap中只剩下 k 個元素，且這些元素是目前遇到的最大的 k 個。
   • 因為是minHeap，因此heap頂端的元素是這些前 k 大元素中的最小值，也就是整個鎮列中的第 k 大元素。
4. 回傳結果：
   • 最後，我們回傳heap頂端元素，它即是第 k 大的元素。

程式碼二

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); //建立一個最小堆用於存儲前k大的元素
        
        //遍歷陣列中每個元素
        for (int num : nums) {
            minHeap.offer(num); //將元素加入最小堆
            //如果堆的大小超過了k，則移除堆頂元素，這樣堆中只保留k個最大的元素
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        
        return minHeap.peek(); //堆頂元素即為第 k 大的元素
    }
}

結論： 在寫這題目時，快速排序法和minHeap法各有千秋，取決於你要如何「找出第 k 大的元素」。快速排序法就像你在整理衣櫃時，將衣服分成左右兩邊，重複這個過程直到找到你最想要的那件（第 k 大元素），它的平均時間快（O(n)），但萬一選錯了「樞紐」（衣服），可能會變慢（O(n²)）。minHeap法則像是你只拿一小堆你最喜歡的衣服（前 k 大元素），每次都只保留那堆裡最差的（minHeap），最後剩下的堆頂就是你要找的。這種方法適合大數據，因為你不必完全整理整個衣櫃，時間相對穩定（O(n log k)）。