Can someone help me with time complexity of my solution?


  • 1
    V
    
    
        public List<Integer> topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> map = new HashMap();
            
            for(int i:nums){
                if(!map.containsKey(i)) map.put(i,1);
                else{
                    int t = map.get(i);
                    map.put(i,t+1);
                }
            }
            
            Queue<Integer[]> q = new PriorityQueue(new Comparator<Integer[]>(){
                @Override
                public int compare(Integer[] i1, Integer[] i2){
                    return i1[1]-i2[1];
                }
            });
            
            for(Map.Entry<Integer, Integer> i: map.entrySet()){
                if(q.size() == k){
                    if(i.getValue() > q.peek()[1]){
                        q.poll();
                        q.offer(new Integer[]{i.getKey(), i.getValue()});
                    }else continue;
                }else q.offer(new Integer[]{i.getKey(), i.getValue()});
            }
            
            List<Integer> ans = new ArrayList();
            
            int n=q.size();
            for(int i=0; i<k; i++){
                ans.add(q.poll()[0]);
            }
            
            return ans;
        }
    

  • 0
    P
    This post is deleted!

  • 1
    L

    @varun50 It is O(nlogK).


Log in to reply
 

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