Java O(n + klog(n - k)) solution Using PriorityQueue and HashMap


  • 3
    A
    • First, iterate the given array once to get key-value pairs where key represents the num in the given array and value means the corresponding frequence;
    • Second, store these key-value pairs into priority queue which is in descending order;
    • Finally, poll the queue k times.
    public List<Integer> topKFrequent(int[] nums, int k) {
            Queue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
                @Override
                public int compare(int[] q1, int[]q2) {
                    return q2[1] - q1[1];
                }
            });
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for (int num : nums) {
                if (map.containsKey(num)) {
                    map.put(num, map.get(num) + 1);
                } else {
                    map.put(num, 1);
                }
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                queue.offer(new int[]{entry.getKey(), entry.getValue()});
            }
            
            List<Integer> result = new ArrayList<Integer>();
            while (result.size() < k) {
                result.add(queue.poll()[0]);
            }
            return result;
        }
    

  • 1
    Z

    Amaaaaaaazing


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.