347. Top K Frequent Elements

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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]

Constraints:

• $1 <= nums.length <= 10^5$
• $-10^4 <= nums[i] <= 10^4$
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Code

692. Top K Frequent Words

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        List<List<Integer>> buckets = new ArrayList<>();
        buckets.add(new ArrayList<>());

        Map<Integer, Integer> counts = new HashMap<>();

        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
            buckets.add(new ArrayList<>());
        }

        for (int num : counts.keySet()) {
          int count = counts.get(num);
          buckets.get(count).add(num);
        }

        int[] res = new int[k];
        for (int i = buckets.size() - 1; i > 0; i--) {
            if(k <= 0) return res;
            if(buckets.get(i).size() == 0) continue;
            for(int num : buckets.get(i)) {
                res[--k] = num;
            }
        }

        return res;
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();

        HashMap<Integer, Integer> map = new HashMap<>();
        for(int num : nums){
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));

        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            queue.offer(entry);
        }

        for(int i = 0; i < k; i++){
            res.add(queue.poll().getKey());
        }

        int[] arr = new int[res.size()];
        for(int i = 0; i < arr.length; i++) {
            arr[i] = res.get(i);
        }

        return arr;
    }
}