力扣347——前 K 個高頻元素

這道題主要涉及的是對數據結構裡哈希表、小頂堆的理解，優化時可以參考一些排序方法。

原題

給定一個非空的整數數組，返回其中出現頻率前 k 高的元素。

示例 1:

<code>
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
/<code>

示例 2:

<code>
輸入: nums = [1], k = 1
輸出: [1]
/<code>

說明：

• 你可以假設給定的 k 總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。
• 你的算法的時間複雜度必須優於 O(n log n) , n 是數組的大小。

原題url：
https://leetcode-cn.com/problems/top-k-frequent-elements/

解題

正常思路

為了解決這道題，我們首先需要知道每個元素出現的次數。最方便的話，可以使用哈希表，因為這就是一個數字——出現次數的映射關係。此處的時間複雜度為O(n)

其次，因為需要查找頻率前 k 高的元素，所以我們肯定是需要排序的，時間複雜度為O(n log n)的排序方法有許多，快速排序、堆排序等，我是用的堆排序，使用小頂堆，這樣在每次入堆的時候，檢查一下堆的個數是否超過 k，如果超過，則移除堆頂的元素(也就是次數最少的元素)。

這樣堆裡剩餘的元素也就是最終的結果了，接下來我們看看代碼：

<code>
class
 
Solution
 {

    
public
 List 
topKFrequent
(
int
[] nums, 
int
 k) {
         
        Map countMap = 
new
 HashMap<>();
        
for
 (
int
 num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 
0
) + 
1
);
        }

         
        PriorityQueue heap = 
new
 PriorityQueue((n1, n2) -> countMap.
get
(n1) - countMap.
get 
(n2));
        Set keySet = countMap.keySet();
        
for
 (
int
 key : keySet) {
            heap.
add
(key);
             
            
if
 (heap.size() > k) {
                heap.poll();
            }
        }
        
        List result = 
new
 LinkedList<>();
        Iterator iterator = heap.iterator();
        
while
 (iterator.hasNext()) {
            result.
add
(iterator.next());
        }

        
return
 result;
    }
}/<code>

提交OK。

桶排序優化

針對排序，我想到了一個優化，利用桶排序，其時間複雜度為O(n)，主要是浪費空間，因為需要申請額外的數組，下標代表出現的次數，元素我用的是 LinkedList，這樣可以存儲多個。那麼這個在進行輸出時，只要從後往前進行遍歷，當結果的數量達到 k 時，就可以停止了。

接下來我們看看代碼 ：

<code>
class
 
Solution
 {

    
public
 List topKFrequent(
int
[] nums,  
int
 k) {
         
        Map countMap = 
new
 HashMap<>();
         
        
int
 maxCount = 
0
;
        
for
 (
int
 num : nums) {
            
int
 count = countMap.getOrDefault(num, 
0
) + 
1
;
            
if
 (count > maxCount) {
                maxCount = count;
            }
            countMap.put(num, count);
        }

         
        LinkedList[] 
array
 = 
new
 LinkedList[maxCount + 
1
];
        
for
 (Map.Entry entry : countMap.entrySet()) {
            
int
 key = entry.getKey();
            
int
 count = entry.getValue();
            LinkedList 
list
 = 
array
[count];
            
if
 (
list
 == null) {
                
list
 = 
new
 LinkedList<>();
                
array
[count] = 
list
;
            }
             
list
.add(key);
        }

         
        List result = 
new
 LinkedList<>();
        
for
 (
int
 i = 
array
.length - 
1
; i >= 
0
 && result.size() < k; i--) {
            List 
list
 = 
array
[i];
            
if
 (
list
 == null) {
                
continue
;
            }

            result.addAll(
list
);
        }

        
return
 result;
    }
}/<code>

提交OK。

總結

以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要涉及的是對數據結構的理解，優化時可以參考一些特殊的排序方法。

有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號，說不定會有意外的驚喜。

https://death00.github.io/

關鍵字: 元素 count nums