215. Kth Largest Element in an Array
1.題目:第 K 大的元素(Leetcode 215)
給定一個整數陣列 nums 和一個整數 k,請你找出陣列中第 k 大的元素(注意是排序後的第 k 大,不是第 k 個不重複的元素)。
解法一:使用 最小堆(Min Heap)
這是一種比排序更有效率的方法。時間複雜度是 O(n log k),比排序的 O(n log n) 更快。
2.思路:
1.我們維護一個「最小堆(Min Heap)」來存放目前最大的 k 個元素。
2.每讀到一個元素就加入堆中。
3.如果堆的大小超過 k,就移除最小的那一個(堆頂)。
4.最後堆頂的元素就是第 k 大的數。
3.範例:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
說明:排序後為 [1,2,3,4,5,6],第 2 大的是 5。
4.程式碼截圖:
5.學習心得:今天的題目我覺得相對比較友善一點,有請AI給我提示,而不是直接給我答案,我覺得這次成就感很足,希望之後每一次的練習我都能有這樣的感覺。