LC 347 - K most Frequent - java - study code - using quick sort partition - http://unknown66.blogspot.ca/2016/05/leetcode-347-top-k-frequent-elements.html

LC347KMostFrequentQsort.java

public class Solution {
    // Pair class, a helper class
    private class Pair {
        int num, freq; // value and its frequency
        public Pair(int val) {
            num = val;
            freq = 1;
        }
    }
    
    public List<Integer> topKFrequent(int[] nums, int k) {
        // value to array index map
        Map<Integer, Integer> map = new HashMap<>();
        // array
        Pair[] pairs = new Pair[nums.length];
        
        int idx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                // got this value before, update frequency
                pairs[map.get(nums[i])].freq++;
            } else {
                // create a new one
                Pair pair = new Pair(nums[i]);
                pairs[idx] = pair;
                map.put(nums[i], idx);
                idx++;
            }
        }
        
        List<Integer> ret = new ArrayList<>();
        if (k >= idx) { // special case: K is greater than unique members
            for (int i = 0; i < idx; i++) {
                ret.add(pairs[i].num);
            }
            
            return ret;
        }
        
        int j = 0, low = 0, high = idx-1;
        k = idx - k;
        while ((j = partition(pairs, low, high)) != k) {
            // quick sort routine -- partition to find index k
            if (j < k) {
                low = j+1;
            } else {
                high = j - 1;
            }
        }
        
        for (; k < idx; k++) {
            // copy final results
            ret.add(pairs[k].num);
        }
        
        return ret;
    }
    
    private int partition(Pair[] pairs, int low, int high) {
        // partition array into two parts, [low..i] contains values
        // <= i, [i+1..high] contains values > i
        Pair x = pairs[low];
        int i = low;
        for (int j = i + 1; j <= high; j++) {
            Pair y = pairs[j];
            if (y.freq <= x.freq) {
                Pair t = pairs[i+1];
                pairs[i+1] = pairs[j];
                pairs[j] = t;
                i++;
            }
        }
        
        pairs[low] = pairs[i];
        pairs[i] = x;
        
        return i;
    }
}