Leetcode - Minimum Increment to Make Array Unique
Leetcode - Task Scheduler

Leetcode - Top K Frequent Elements

violet posted @ Jul 23, 2020 08:28:32 AM in 算法 with tags Algorithm Heap Java , 10574 阅读

https://leetcode.com/problems/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]

 

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        PriorityQueue<Num> pq = new PriorityQueue<>(Collections.reverseOrder());
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            if (map.containsKey(n)) {
                map.put(n, map.get(n)+1);
            } else {
                map.put(n, 1);
            }
        }
        for (int i : map.keySet()) {
            pq.add(new Num(i, map.get(i)));
        }
        int len = k;
        if (pq.size() < k) len = pq.size();
        int[] result = new int[len];
        for (int i = 0; i < k && !pq.isEmpty(); i++) {
            Num num = pq.poll();
            int n = num.num;
            int freq = num.freq;
            result[i] = num.num;
        }
        return result;
    }
    private class Num implements Comparable<Num> {
        public int num;
        public int freq;
        public Num(int num, int freq) {
            this.num = num;
            this.freq = freq;
        }
        @Override
        public int compareTo(Num that) {
            return this.freq - that.freq;
        }
    }
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter