Java O(n) solution using hash map and quickselect


  • 0
    E

    public class Solution {

    private ArrayList<Integer> res = new ArrayList<Integer>();
    
    public List<Integer> topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        ArrayList<Integer> uniqueNums = new ArrayList<Integer>();
        
        // construct the map of <number, frequency>
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i])+1);
            } else {
                uniqueNums.add(nums[i]);
                map.put(nums[i], 1);
            }
        }
        
        // find top k frequent number from uniqueNums list according to their freq in map
        return findTopKFrequent(uniqueNums, map, k, 0, uniqueNums.size()-1);
    }
    
    /* quickSelect
     */
    private ArrayList<Integer> findTopKFrequent(ArrayList<Integer> uniqueNums, HashMap<Integer, Integer> map, int k, int start, int end) {
        
        if (k == 0) return res;
        
        int left = start, pivot = map.get(uniqueNums.get(end));
        
        for (int i = start; i < end; i++) {
            if (map.get(uniqueNums.get(i)) > pivot) {
                Collections.swap(uniqueNums, i, left);
                left++;
            }
        }
        Collections.swap(uniqueNums, left, end);
        
        if (left - start + 1 > k) return findTopKFrequent(uniqueNums, map, k, start, left - 1);
        else {
            for (int j = start; j < left + 1; j++) {
                res.add(uniqueNums.get(j));
            }
            return findTopKFrequent(uniqueNums, map, k-left+start-1, left+1, end);
        }
    }
    

    }


Log in to reply
 

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