2 Java Solutions


  • 0
    M

    Solution 1. Bucket Sort

    class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            List<Integer> res = new ArrayList<>();        
            if (nums == null || nums.length == 0 || k <= 0) return res;
            int n = nums.length;
            Map<Integer, Integer> hist = new HashMap<>();
            for (int num : nums) {
                hist.put(num, hist.getOrDefault(num, 0) + 1);
            }
            
            if (k >= hist.size()) return new ArrayList<Integer>(hist.keySet());
            List<Integer>[] bucket = new List[n + 1];
            for (int num : hist.keySet()) {
                int cnt = hist.get(num);
                if (bucket[cnt] == null) bucket[cnt] = new ArrayList<Integer>();
                bucket[cnt].add(num);
            }
            for (int i = n; i >= 0 && res.size() < k; --i) {
                if (bucket[i] != null && bucket[i].size() > 0) {
                    res.addAll(bucket[i]);
                    while (res.size() > k) {
                        res.remove(res.size() - 1);
                    }
                }
            }
            return res;
        }    
    }
    

    Solution 2. Quick Select:

    class Solution {
        private class Ele {
            int val;
            int cnt;
            public Ele(int val, int cnt) {
                this.val = val;
                this.cnt = cnt;
            }
        }
        public List<Integer> topKFrequent(int[] nums, int k) {
            List<Integer> res = new ArrayList<>();
            if (nums == null || k <= 0) return res;        
            int n = nums.length;
            Map<Integer, Integer> hist = new HashMap<>();
            for (int num : nums) hist.put(num, hist.getOrDefault(num, 0) + 1);
            if (k >= hist.size()) return new ArrayList<Integer>(hist.keySet());
            Ele[] arr = new Ele[hist.size()];
            int ind = 0;
            for (int num : hist.keySet()) {
                arr[ind++] = new Ele(num, hist.get(num));
            }
            
            int lo = 0, hi = hist.size() - 1;
            while (lo < hi) {
                int p = partition(arr, lo, hi);
                if (p == k - 1) break;
                if (p < k - 1) {
                    lo = p + 1;
                } else {
                    hi = p - 1;
                }
            }
            for (int i = 0; i < k; ++i) {
                res.add(arr[i].val);
            }
            return res;
        }
        private int partition(Ele[] arr, int lo, int hi) {
            int pivot = arr[hi].cnt;
            int i = lo - 1;
            for (int j = lo; j < hi; ++j) {
                if (arr[j].cnt > pivot) {                
                    swap(arr, ++i, j);
                }
            }
            swap(arr, ++i, hi);
            return i;
        }
        private void swap(Ele[] arr, int i, int j) {
            if (i == j) return;
            Ele temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    

Log in to reply
 

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