给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

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

输入: nums = [1], k = 1
输出: [1]
说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

解法一：

使用 Hashmap，建立数组中元素与其出现次数的映射。然后建立一个拥有 n 个列表的列表 lists，n 代表数组的长度，然后遍历 Hashmap，将出现次数相同的元素保存到同一个列表中，这里的列表为 lists 中下标为出现次数 -1 的列表。最后反向遍历 lists，将出现次数最大的 k 个元素加入 list 中。

    public List<Integer> topKFrequent(int[] nums, int k) {

        HashMap<Integer, Integer> hashMap = new HashMap<>();

        List<List<Integer>> lists = new ArrayList<>();

        List<Integer> list = new ArrayList<>();

        int max = 0;

        for (int i = 0; i < nums.length; i++) {
            if (!hashMap.containsKey(nums[i])) {
                hashMap.put(nums[i], 1);
            } else {
                hashMap.replace(nums[i], hashMap.get(nums[i]) + 1);
            }
        }

        Iterator iterator = hashMap.entrySet().iterator();

        for (int i = 0; i < nums.length; i++) {
            List<Integer> list1 = new ArrayList<>();
            lists.add(list1);
        }

        while (iterator.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator.next();

            max = Math.max(max, (Integer) entry.getValue());

            lists.get((Integer) entry.getValue() - 1).add((Integer) entry.getKey());
        }

        for (int i = lists.size() - 1; i >= 0; i--) {

            for (int j = 0; j < lists.get(i).size(); j++) {
                if (list.size() == k) {
                    break;
                }
                list.add(lists.get(i).get(j));
            }
        }
        return list;
    }

解法二：

我们还可以使用优先队列来做，使用一个最大堆按照映射次数从大到小排列。这里我们需要自己创建一个 Pair 类，因为 Java 自身提供的 Pair 类是不支持元素比较的。我们还需要实现 Comparable 接口，需要注意的是 compareTo 方法： 如果返回值大于 0，则将大的数放后面；如果返回值等于 0，则不做任何处理；如果返回值小于 0，则将小的数放前面。就是说 java 默认的排序方式是升序排序，而我们要的是降序排序。代码如下：

    public List<Integer> topKFrequent(int[] nums, int k) {

        PriorityQueue<Pair> queue = new PriorityQueue<>();

        HashMap<Integer, Integer> hashMap = new HashMap<>();

        List<Integer> list = new ArrayList<>();


        for (int i = 0; i < nums.length; i++) {
            if (!hashMap.containsKey(nums[i])) {
                hashMap.put(nums[i], 1);
            } else {
                hashMap.replace(nums[i], hashMap.get(nums[i]) + 1);
            }
        }

        Iterator iterator = hashMap.entrySet().iterator();

        while (iterator.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator.next();

            queue.add(new Pair((Integer) entry.getKey(), (Integer) entry.getValue()));
        }

        for (int i = 0; i < k; i++) {
            list.add(queue.poll().getKey());
        }

        return list;
    }

    class Pair implements Comparable<Pair> {

        private Integer key;
        private Integer value;

        public Pair(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }

        public Integer getValue() {
            return value;
        }

        public Integer getKey() {
            return key;
        }

        @Override
        public int compareTo(Pair o) {
            if (this.value > o.getValue()) {
                return -1;
            } else if (this.value < o.getValue()) {
                return 1;
            } else {
                return 0;
            }
        }
    }