Leetcode

347. Top K Frequent Elements

by hooni posted Apr 14, 2020
?

단축키

Prev이전 문서

Next다음 문서

ESC닫기

크게 작게 위로 아래로 댓글로 가기 인쇄

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 List<Integer> topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> hmap = new HashMap<Integer, Integer>();
        List<Integer> result = new ArrayList<Integer>();
        int topK = 0;

        for(int i=0; i<nums.length; i++){
            if(hmap.containsKey(nums[i])){
                hmap.put(nums[i], hmap.get(nums[i])+1);
            }else{
                hmap.put(nums[i], 1);
            }
        }
        
        for(int i=0; i<k; i++){
            int maxKey = 0;
            int maxValue = 0;
            /*
            // Getting a Set of Key-value pairs
            Set entrySet = hmap.entrySet();
            Iterator it = entrySet.iterator();
            while(it.hasNext()){
                Map.Entry item = (Map.Entry)it.next();
                int value = (int)item.getValue();
                if(value > maxValue){
                    maxKey = (int)item.getKey();
                    maxValue = value;
                }
            }
            */
            for(Map.Entry item : hmap.entrySet()){
                int value = (int)item.getValue();
                if(value > maxValue){
                    maxKey = (int)item.getKey();
                    maxValue = value;
                }
            }
            
            result.add(maxKey);
            //hmap.put(maxKey, -1);
            hmap.remove(maxKey);
        }
        
        return result;
    }
}


class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        //count the frequency for each element
        HashMap<Integer, Integer> hmap = new HashMap<>();
        
        for(int num : nums){
            hmap.put(num, hmap.getOrDefault(num, 0) + 1);
        }
        
        // create a min heap
        PriorityQueue<Map.Entry<Integer, Integer>> queue
            = new PriorityQueue<>(Comparator.comparing(e -> e.getValue()));
        
        //maintain a heap of size k.
        for(Map.Entry<Integer, Integer> item : hmap.entrySet()){
            queue.offer(item);
            if(queue.size() > k){
                queue.poll();
            }
        }
        
        //get all elements from the heap
        List<Integer> result = new ArrayList<>();
        //while(!queue.isEmpty()){
        while(queue.size() > 0){
            result.add(queue.poll().getKey());
        }

        //reverse the order
        Collections.reverse(result);
        
        return result;
    }
}

[문제] https://leetcode.com/problems/top-k-frequent-elements/