前k个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

小根堆

方法1是使用堆，先统计数量然后建一个小根堆，小根堆的最大节点数量是k，从k＋1个元素开始，进来的元素与小根堆的根节点进行比较，若更大，则替换。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }

        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}

快排

基于快速排序，每次递归都可能会减少下一层的数量，平均复杂度同样也是O(n).

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }
        // 获取每个数字出现次数
        List<int[]> values = new ArrayList<int[]>();
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            values.add(new int[]{num, count});
        }
        int[] ret = new int[k];
        qsort(values, 0, values.size() - 1, ret, 0, k);
        return ret;
    }

    public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {
        int picked = (int) (Math.random() * (end - start + 1)) + start;
        Collections.swap(values, picked, start);

        int pivot = values.get(start)[1];
        int index = start;
        for (int i = start + 1; i <= end; i++) {
            // 使用双指针把不小于基准值的元素放到左边，
            // 小于基准值的元素放到右边
            if (values.get(i)[1] >= pivot) {
                Collections.swap(values, index + 1, i);
                index++;
            }
        }
        Collections.swap(values, start, index);

        if (k <= index - start) {
            // 前 k 大的值在左侧的子数组里
            qsort(values, start, index - 1, ret, retIndex, k);
        } else {
            // 前 k 大的值等于左侧的子数组全部元素
            // 加上右侧子数组中前 k - (index - start + 1) 大的值
            for (int i = start; i <= index; i++) {
                ret[retIndex++] = values.get(i)[0];
            }
            if (k > index - start + 1) {
                qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1));
            }
        }
    }
}

非平凡的一种解法，计数排序

计数排序直接使用大量冗余的空间来换取时间，给每一个可能出现的值都预先分配好位置。这样确实会提速不少，不过要慎重使用。下面的例子直接使用了两次计数排序，速度比上面的方法快了10倍。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            if(num>max)
                max = num;
            if(num<min)
                min = num;
        }
        int len = max - min + 1;
        int[] k_v = new int[len];
        for (int num : nums)
            k_v[num - min]++;

        int r_len = Integer.MIN_VALUE;
        for(int num:k_v) {
            if (num > r_len)
                r_len = num;
        }

        ArrayList<Integer>[] reversedKV = new ArrayList[r_len + 1];
        for (int i = 0; i < k_v.length; i++) {
            if (k_v[i] > 0) {
                ArrayList<Integer> o = reversedKV[k_v[i]];
                if (o == null) {
                    o = new ArrayList<>();
                    reversedKV[k_v[i]] = o;
                }
                o.add(min + i);
            }
        }

        int[] r_temp = new int[k];
        int pos = 0;
        for (int i = reversedKV.length - 1; i >= 0 && pos < k; i--) {
            if (reversedKV[i] != null) {
                for (int v : reversedKV[i]) {
                    r_temp[pos++] = v;
                    if (pos >= k)
                        break;
                }
            }
        }

        return r_temp;

    }

}