347. Top K Frequent Elements

Quick select

use quick select is too complex, this Q can be solved by bucket sort.

time: O(n)

space: O(m), map size

idea - use map to count, then gen a new array to do the quick select

just the compare condition becomes like this:

if (count.get(nums[i]) < count.get(nums[pivot]))

class Solution {
    Map<Integer, Integer> count;
    
    public int[] topKFrequent(int[] nums, int k) {
        count = new HashMap();
        for (int num: nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        // array of unique elements
        int n = count.size();
        int[] unique = new int[n]; 
        int i = 0;
        for (int num: count.keySet()) {
            unique[i] = num;
            i++;
        }
        
        findKthSmallest(unique, 0, n - 1, n - k);
        
        return Arrays.copyOfRange(unique, n - k, n);
        
    }
    
    private void findKthSmallest(int nums[], int left, int right, int ksmallest) {
        if (left == right) return; // only one element

        int pivot = partition(nums, left, right);
        
        if (ksmallest == pivot) { // bingo!
            return;
        } else if (ksmallest < pivot) { // find left side
            findKthSmallest(nums, left, pivot - 1, ksmallest);
                
        } else { // find right side
            findKthSmallest(nums, pivot + 1, right, ksmallest);
        }
    }
    
    private int partition(int nums[], int left, int right) {
        int pivot = right;
        int storedIndex = left;
        
        for (int i = left; i < right; i++) {
            if (count.get(nums[i]) < count.get(nums[pivot])) { // here is different
                swap(nums, storedIndex, i);
                storedIndex++;
            }
        }
        swap(nums, storedIndex, pivot);
        return storedIndex;
    }
    
    private void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Random Pivot

class Solution {
    Map<Integer, Integer> count;
    
    public int[] topKFrequent(int[] nums, int k) {
        count = new HashMap();
        for (int num: nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        // array of unique elements
        int n = count.size();
        int[] unique = new int[n]; 
        int i = 0;
        for (int num: count.keySet()) {
            unique[i] = num;
            i++;
        }
        
        findKthSmallest(unique, 0, n - 1, n - k);
        
        return Arrays.copyOfRange(unique, n - k, n);
        
    }
    
    private void findKthSmallest(int nums[], int left, int right, int ksmallest) {
        if (left == right) return; // only one element

        Random random = new Random();
        int randomPivot = left + random.nextInt(right - left);
        int pivot = partition(nums, left, right, randomPivot);
        
        if (ksmallest == pivot) { // bingo!
            return;
        } else if (ksmallest < pivot) { // find left side
            findKthSmallest(nums, left, pivot - 1, ksmallest);
                
        } else { // find right side
            findKthSmallest(nums, pivot + 1, right, ksmallest);
        }
    }
    
    private int partition(int nums[], int left, int right, int pivot) {
        int pivotVal = count.get(nums[pivot]);
        swap(nums, pivot, right);
        int storedIndex = left;
        
        for (int i = left; i < right; i++) {
            if (count.get(nums[i]) < pivotVal) { // here is different
                swap(nums, storedIndex, i);
                storedIndex++;
            }
        }
        swap(nums, storedIndex, right);
        return storedIndex;
    }
    
    private void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}