Java fast O(n) Solution, Quick Select Algorithm


  • 0
    Z

    The idea is simple, we collect map of frequencies, then find kth largest element by frequency (kth frequent element). After that just collect elements standing righter than the kth largest one to the result list. Average running time of the algorithm is O(n).

    public class Solution {
       class Entry implements Comparable<Entry>{
           Integer val, freq;
           public Entry(int val , int freq){
               this.val = val;
               this.freq = freq;
           }
           
           @Override
           public int compareTo(Entry a){
                return freq.compareTo(a.freq);
           }
       }
        
        public List<Integer> topKFrequent(int[] nums, int k) {
            List<Integer> res = new ArrayList<>();
            if(nums == null || nums.length == 0) return res;
            Map<Integer, Integer> freqMap = new HashMap<>();
            for(int i = 0;i<nums.length;i++){
                if(freqMap.containsKey(nums[i])){
                    freqMap.put(nums[i],freqMap.get(nums[i])+1);
                } else {
                    freqMap.put(nums[i],1);
                }
            }
            Entry[] entries = new Entry[freqMap.keySet().size()];
            int i = 0;
            for(Integer key:freqMap.keySet()){
                entries[i++] = new Entry(key, freqMap.get(key));
            }
            quickFill(entries,res, entries.length-k, 0, entries.length-1);
            return res;
        }
    
        public void swap(Entry[] entries, int i , int j){
            Entry tmp = entries[i];
            entries[i] = entries[j];
            entries[j] = tmp;
        }
    
        public int partition(Entry[] entries, int start, int end){
            int pivot = end;
            int i = start;
            for(int j = start;j<end;j++){
                if(entries[pivot].compareTo(entries[j]) == 1){
                    swap(entries, i , j);
                    i++;
                } 
            }
            swap(entries, i, pivot);
            return i;
        }
        
        public void quickFill(Entry[] entries, List<Integer> res, int k, int start, int end){
            int pivot = partition(entries, start, end);
            if(pivot == k){
                for(int i = k;i<entries.length;i++){
                    res.add(entries[i].val);
                }
            } else if(pivot>k){
                quickFill(entries, res, k, start, pivot-1);
            } else {
                quickFill(entries, res, k, pivot+1, end);
            }
        }
    }

Log in to reply
 

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