【leetcode每日刷题】347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
class Solution {
    public ArrayList<Integer> topKFrequent(int[] nums, int k) {
        ArrayList<Integer> array = new ArrayList<Integer>();
        if(nums.length == 0) return array;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int num: nums){
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2) -> map.get(n2) - map.get(n1));
        for(int num: map.keySet()){
            heap.add(num);
        }
        while(k-- > 0){
            array.add(heap.poll());
        }
        return array;
    }
}

使用优先队列对map中的值进行排序,然后获得钱k个元素。

上一篇:【leetcode】347. Top K Frequent Elements


下一篇:347. 前K个高频元素