@@ -0,0 +1,2713 @@
+import org.junit.After;%0Aimport org.junit.Assert;%0Aimport org.junit.Before;%0Aimport org.junit.Test;%0A%0Aimport java.util.*;%0A%0A/**%0A * Given a non-empty array of integers, return the k most frequent elements.%0A * %3Cp%3E%0A * For example,%0A * Given %5B1,1,1,2,2,3%5D and k = 2, return %5B1,2%5D.%0A * %3Cp%3E%0A * Note:%0A * You may assume k is always valid, 1 %E2%89%A4 k %E2%89%A4 number of unique elements.%0A * Your algorithm's time complexity must be better than O(n log n), where n is the array's size.%0A * %3Cp%3E%0A * Tags: Hash Table, Heap%0A * Similar Problems: (M) Word Frequency, (M) Kth Largest Element in an Array%0A */%0Apublic class TopKFrequentElements %7B%0A%0A    private TopKFrequentElements t;%0A%0A    /**%0A     * Use a map to store frequency.%0A     * Create a bucket of lists, indexed by frequency.%0A     * Each list contains the number of that frequency.%0A     */%0A    public List%3CInteger%3E topKFrequent(int%5B%5D nums, int k) %7B%0A        if (nums == null %7C%7C nums.length == 0) return Collections.emptyList();%0A        // Build frequency map%0A        Map%3CInteger, Integer%3E frequencyMap = new HashMap%3C%3E();%0A        for (int n : nums) %7B%0A            frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);%0A        %7D%0A        // Build frequency buckets%0A        List%3CInteger%3E%5B%5D lists = new List%5Bnums.length + 1%5D;%0A        for (Map.Entry%3CInteger, Integer%3E e : frequencyMap.entrySet()) %7B%0A            int frequency = e.getValue();%0A            if (lists%5Bfrequency%5D == null) lists%5Bfrequency%5D = new ArrayList%3C%3E();%0A            lists%5Bfrequency%5D.add(e.getKey());%0A        %7D%0A        // Add top k most frequent integer to result%0A        List%3CInteger%3E res = new ArrayList%3C%3E();%0A        for (int i = lists.length - 1; i %3E= 0; i--) %7B%0A            if (lists%5Bi%5D == null) continue;%0A            for (int j = 0; j %3C lists%5Bi%5D.size() && res.size() %3C k; j++) %7B%0A                res.add(lists%5Bi%5D.get(j));%0A            %7D%0A        %7D%0A        return res;%0A    %7D%0A%0A    @Before%0A    public void setUp() %7B%0A        t = new TopKFrequentElements();%0A    %7D%0A%0A    @Test%0A    public void testInvalidInput() %7B%0A        Assert.assertEquals(Collections.EMPTY_LIST, t.topKFrequent(null, 0));%0A        Assert.assertEquals(Collections.EMPTY_LIST, t.topKFrequent(new int%5B%5D%7B%7D, 0));%0A    %7D%0A%0A    @Test%0A    public void testEdgeCase() %7B%0A        List%3CInteger%3E res = t.topKFrequent(new int%5B%5D%7B1%7D, 1);%0A        Assert.assertEquals(1, res.size());%0A        Assert.assertEquals(1, res.get(0).intValue());%0A    %7D%0A%0A    @Test%0A    public void testExample() %7B%0A        List%3CInteger%3E res = t.topKFrequent(new int%5B%5D%7B1, 1, 1, 2, 2, 3%7D, 2);%0A        Assert.assertEquals(2, res.size());%0A        Assert.assertEquals(1, res.get(0).intValue());%0A        Assert.assertEquals(2, res.get(1).intValue());%0A    %7D%0A%0A    @After%0A    public void tearDown() %7B%0A        t = null;%0A    %7D%0A%7D%0A

add Top K Frequent Elements