leetcode 347. Top K Frequent Elements

Seawolf

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.

using regular hashmap!

import java.util.Collection;
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        HashMap <Integer,Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++){
            map.put(nums[i], map.getOrDefault(nums[i],0)+1);
        }
        Collection<Integer> c = map.values();
        Object[] obj = c.toArray();
        Arrays.sort(obj);
        int i = 0;
        while(k-- != 0){
            for(Integer key : map.keySet()){
                if (map.get(key).equals(Integer.parseInt(obj[obj.length- 1-i].toString())))
                {
                    
                    i++;
                    list.add(key);
                    map.remove(key);
                    break;
                }    
            } 
        }
        return list;
    }
}

using bucket sort!!

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int a : nums) map.put(a,map.getOrDefault(a,0)+1);
        List<Integer> [] bucket = new List[nums.length + 1];
        
        for(Integer key : map.keySet()){
            
            int fre = map.get(key);
            if(bucket[fre] == null) bucket[fre] = new ArrayList<>();
            bucket[fre].add(key);
        }
        List<Integer> re = new ArrayList<>();
        
        for(int i = bucket.length - 1; i >=0 && re.size() < k ; i--){
            
            if(bucket[i] != null) re.addAll(bucket[i]);
        }
        
        return re;
        
    }
    
}

using java heap!

import java.util.*;
class Solution {
    
    class Pair{
        int num;
        int count;
        public Pair(int num, int count){
            
            this.num = num;
            this.count =count;
        }
    }
    public List<Integer> topKFrequent(int[] nums, int k) {
        
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int a: nums) map.put(a,map.getOrDefault(a,0)+1);
        
        PriorityQueue<Pair> queue = new PriorityQueue<Pair>(new Comparator<Pair>(){
            
            public int compare(Pair a, Pair b){
                
                return a.count- b.count;
            } 
        });
        
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            
            Pair p = new Pair(entry.getKey(), entry.getValue());
            
            queue.offer(p);
            if(queue.size() > k) queue.poll();
        }
        
        List<Integer> list = new ArrayList<>();
        
        while(queue.size()>0) list.add(queue.poll().num);
        
        Collections.reverse(list);
        
        return list;
    }
    
}