LeetCode 347：前k個高頻元素

• • 題目描述
  • 解題思路
  • 代碼實作
  • 總結

題目描述

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

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2

輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1

輸出: [1]

說明：

你可以假設給定的 k 總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。

你的算法的時間複雜度必須優于 O(n log n) , n 是數組的大小。

解題思路

想到可以用hashmap以每個元素為key統計，各個元素出現的頻次，再建構一個小頂堆用來存儲前k個高頻的元素，周遊數組元素，在小頂堆存儲個數小于k時，按序添加，大于k時，比較堆頂元素出現的頻次和周遊元素出現的頻次，如果堆頂元素頻次小于周遊元素的，那麼将堆頂元素彈出後，再将新元素加入堆中！！！

代碼實作

去部落格設定頁面，選擇一款你喜歡的代碼片高亮樣式，下面展示同樣高亮的

代碼片

.

import java.util.*;

public class topKthEle {
    //前k個高頻元素
    public List<Integer> topKFrequent(int[] nums,int k){//acc: 24ms 53%
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int num:nums){  //統計nums數組中，各數字出現的頻次
            if (map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else {
                map.put(num,1);
            }
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1)-map.get(o2);
            }
        });

        for (Integer key:map.keySet()){ //将出現頻次最高的k個元素裝入小頂堆中
            if (pq.size()<k){
                pq.add(key);
            }else if (map.get(key)>map.get(pq.peek())){
                pq.remove();
                pq.add(key);
            }
        }

        List<Integer> res=new ArrayList<>();
        while (!pq.isEmpty()){
            res.add(pq.remove());
        }
        return res;
    }
    public static void main(String[] args) {
        topKthEle test=new topKthEle();
        int[] nums={1,3,2,1,3,1,5};
        List<Integer> list=test.topKFrequent(nums,2);
        System.out.println(list);
    }
}

           

總結

本題來源于Leetcode中 歸屬于堆類型題目。

同許多在算法道路上不斷前行的人一樣，不斷練習，修煉自己！

如有部落格中存在的疑問或者建議，可以在下方留言一起交流，感謝各位！

覺得本部落格有用的客官，可以給個贊鼓勵下！ 嘿嘿