Java O(n) solution with O(n) extra memory: k-th order statistics


  • 0
    A

    The idea is to use algorithm for finding kth-order statistics in array.

    1. Create frequency map: go through array and count each element in Map<Integer, Integer> - O(n)
    2. Create array of pairs from that map, such that each pair is (v,f) - where v -actual value, f - number of times that this value appears in array. O(n)
    3. Using 'quicksort' like algorithm find k-th element in array of pairs (where key is frequency) (details about algorithm) - O(n)
    4. Now all elements before that k-th element will be most frequent values in a array
    class Solution {
        
        /*
         * Aux class to store tuble (v, f) - where
         * v - actual value, f - number of times that value 'v'
         * appears in array
         */
        class Pair{
            
            final int freq;
            final int val;
            
            Pair(int val, int freq){
                this.val = val;
                this.freq = freq;
            }
        }
        
        static Random rnd = new Random();
        
        public List<Integer> topKFrequent(int[] nums, int k) {
            if(nums.length == 1) return Arrays.asList(nums[0]);
            Map<Integer, Integer> freqMap = createFreqMap(nums);
            // array of frequencies from freqMap
            Pair[] pairs = new Pair[freqMap.size()];        
            int j = 0;
            for(Integer kk: freqMap.keySet()){
                pairs[j++] = new Pair(kk, freqMap.get(kk));
            }        
            if(pairs.length == 1) return Arrays.asList(pairs[0].val);
            // here we are trying to find k-th ordeer statistics
            int low = 0;
            int high = pairs.length;
            while (true) {
               if(high <= low) break;
               int n = randomizedPartition(pairs, low, high);
               if (k < n)
                high = n;
               else if (k > n)
                low = n + 1;
               else
                break;
            }
            List<Integer> result = new LinkedList<>();
            for(int jj=0;jj<k;jj++){
                result.add(pairs[jj].val);
            }
            return result;
        }
    
      /*
       * Frequency map, where key is actual value from int[] nums
       * and value is number of times that value appears in int[] nums.
       * Complexity - O(n)
       */
      static Map<Integer, Integer> createFreqMap(int[] nums) {
        Hash<Integer, Integer> freqMap = new HashMap<>();
        for(Integer n: nums){
          frqMap.put(n, freqMap.getOrDefault(n, 0) + 1);
        }    
        return freqMap;
      }
        
      static int randomizedPartition(Pair[] a, int low, int high) {
        swap(a, low + rnd.nextInt(high - low), high - 1);
        Pair separator = a[high - 1];
        int i = low - 1;
        for (int j = low; j < high; j++)
          if (a[j].freq >= separator.freq)
            swap(a, ++i, j);
        return i;
      }    
    
      static void swap(Pair[] a, int i, int j) {
        Pair t = a[i];
        a[i] = a[j];
        a[j] = t;
      }
        
    }
    

Log in to reply
 

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