一. 题目

二. 思路

1. 堆

2. 快排

3. 桶排序

• 哈希统计数量，然后将其放到数量-1的索引位置，最后遍历后k个数。O(n)时间复杂度。

三. 代码

1. 堆

class Solution
{
    final Map<Integer, Integer> cnt = new HashMap<>();
    final Queue<Map.Entry<Integer, Integer>> q = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

    public int[] topKFrequent(int[] nums, int k)
    {
        cnt.clear();
        q.clear();
        for (Integer v : nums)//统计次数
            cnt.put(v, cnt.getOrDefault(v, 0) + 1);

        for (Map.Entry<Integer, Integer> e : cnt.entrySet())
            if (q.size() < k) q.offer(e);
            else
            {
                Map.Entry<Integer, Integer> minv = q.peek();
                if (minv.getValue() < e.getValue())
                {
                    q.poll();
                    q.offer(e);
                }
            }
        return q.stream().mapToInt(Map.Entry::getKey).toArray();
    }
}

2. 快排

class Solution
{
    static final ThreadLocalRandom rnd = ThreadLocalRandom.current();
    final Map<Integer, Integer> cnt = new HashMap<>();
    final List<Map.Entry<Integer, Integer>> a = new ArrayList<>();

    private void quickSort(int l, int r, int k)//逆序排，这样前k大的就是数组前k个
    {
        if (l >= r) return;
        int mi = rnd.nextInt(l, r + 1);
        Map.Entry<Integer, Integer> mv = a.get(mi);
        Collections.swap(a, mi, l);//交换首和轴

        int i = l, j = r;
        while (i < j)
        {
            while (i < j && a.get(j).getValue() <= mv.getValue()) --j;
            Collections.swap(a, i, j);

            while (i < j && a.get(i).getValue() >= mv.getValue()) ++i;
            Collections.swap(a, i, j);
        }
        a.set(i, mv);

        int c = i - l + 1;
        if (c == k) return;
        if (c < k) quickSort(i + 1, r, k - c);
        else quickSort(l, i - 1, k);
    }

    public int[] topKFrequent(int[] nums, int k)
    {
        a.clear();
        cnt.clear();
        for (Integer v : nums)//统计次数
            cnt.put(v, cnt.getOrDefault(v, 0) + 1);

        a.addAll(cnt.entrySet());
        quickSort(0, a.size() - 1, k);
        return a.stream().limit(k).mapToInt(Map.Entry::getKey).toArray();
    }
}

3. 桶排序

class Solution
{
    static final ThreadLocalRandom rnd = ThreadLocalRandom.current();
    final Map<Integer, Integer> cnt = new HashMap<>();

    public int[] topKFrequent(int[] nums, int k)
    {
        cnt.clear();
        for (Integer v : nums)//统计次数
            cnt.put(v, cnt.getOrDefault(v, 0) + 1);

        List<Integer>[] a = (List<Integer>[]) new List[nums.length];
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet())
        {
            int key = entry.getKey(), value = entry.getValue() - 1;
            if (a[value] == null) a[value] = new ArrayList<>();
            a[value].add(key);
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = nums.length - 1; ans.size() < k; --i)
            if (a[i] != null)
                ans.addAll(a[i]);
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}