16 ms java solution


  • 0
    I

    using sort and min heap

    import java.util.*;
    public class Solution {
        public class Freq {
            public int value;
            public int count;
            public Freq(int value, int count) {
                this.value = value;
                this.count = count;
            }
        }
        
        public List<Integer> topKFrequent(int[] nums, int k) {
            Arrays.sort(nums);
            
            Freq[] heap = new Freq[k];
            for (int i = 0; i < k; i++) {
                heap[i] = new Freq(0, 0);
            }
            
            int last = nums[0];
            int count = 0;
            for (int i = 0 ; i < nums.length; i++) {
                if (last == nums[i]) {
                    count++;
                } else {
                    if(count > heap[0].count) {
                        heap[0].count = count;
                        heap[0].value = last;
                        reorganize(heap, 0);
                    }
                    last = nums[i];
                    count = 1;
                }
            }
            
            if(count > heap[0].count) {
                heap[0].count = count;
                heap[0].value = last;
                reorganize(heap, 0);
            }
            
            
            Arrays.sort(heap, new Comparator<Freq>() {
                public int compare(Freq a, Freq b) {
                    return b.count - a.count;
                }
            });
            List<Integer> topK = new LinkedList<Integer>();
            for (int i = 0; i < k; i++) {
                topK.add(heap[i].value);
            }
            return topK;
        }
        
        public void reorganize(Freq[] heap, int p) {
            if (p >= heap.length) {
                return;
            }
            int left = p * 2 + 1;
            int right = p * 2 + 2;
            if (left >= heap.length) {
                return;
            } else if (right >= heap.length) {
                if (heap[p].count > heap[left].count) {
                    Freq t = heap[p];
                    heap[p] = heap[left];
                    heap[left] = t;
                }
            } else {
                int min = p;
                if (heap[min].count > heap[left].count) {
                    min = left;
                }
                if (heap[min].count > heap[right].count) {
                    min = right;
                }
                if (min != p) {
                    Freq t = heap[p];
                    heap[p] = heap[min];
                    heap[min] = t;
                    reorganize(heap, min);
                }
            }
        }
    }

  • 0
    Z

    The running time of sort is O(nlogn)..


Log in to reply
 

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