題目
#

leetcode 215 - Kth Largest Element in an Array (題目說明請點連結)

題目簡述
#

給定一個整數陣列 nums 和一個整數 k，找到陣列中第 k 大的元素。

範例
#

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Explanation: 數組中第 2 大的元素是 5。

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Explanation: 數組中第 4 大的元素是 4。

解題思路
#

題目要求找到數組中第 k 大的元素。可以使用多種方法來解決此問題，常見的解法有以下兩種：

排序法：將數組排序，然後選擇第 k 大的元素。
堆法：使用最小堆（Min-Heap）來解決，堆中始終保持 k 個最大元素，最小堆的根元素即為第 k 大的元素。

在這裡，我們選擇使用 最小堆，因為這樣可以達到更高效的時間複雜度。具體步驟如下：

解法
#

初始化一個最小堆（Min-Heap）。
遍歷數組中的每個元素：
- 如果堆的大小小於 k，將當前元素加入堆中。
- 如果堆的大小達到 k，並且當前元素大於堆頂元素（最小值），則將堆頂元素移除並將當前元素加入堆中。
當所有元素遍歷完成後，堆頂元素即為第 k 大的元素。

這樣我們就能在 O(n log k) 的時間複雜度內找到第 k 大的元素。

完整程式碼
#

java

import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        // 遍歷數組中的每個元素
        for (int num : nums) {
            // 如果堆的大小小於 k，直接插入元素
            if (heap.size() < k || heap.peek() <= num) {
                heap.offer(num);
            }

            // 如果堆的大小超過 k，移除堆頂最小元素
            if (heap.size() > k) {
                heap.poll();
            }
        }

        // 返回堆頂元素，即為第 k 大的元素
        return heap.peek();
    }
}