leetcode-347. 前 K 个高频元素

347. 前 K 个高频元素

• 建立一个map集合第一个元素代表当前的数字，第二个元素代表出现的次数
• 以元素出现次数作为排序标准建立小根堆
• 遍历map加入到堆中，当堆的长度为k的时候，堆中存储的就是当前的前K个高频元素，堆顶是出现次数最少的元素
• 当遍历到下一个map元素，比较一下当前数出现次数与堆顶的数出现次数，如果大于当前堆顶，就移除堆顶，将当前数加入堆

public int[] topKFrequent(int[] nums, int k) {
        //第一个元素代表当前的数字，第二个元素代表出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if(map.containsKey(num)){ //如果这个数字已经存在于map中了，就让第二个元素++
                map.put(num, map.get(num) + 1);
            }else {
                map.put(num, 1); //如果不在就设为1
            }
        }
        //数组第一个元素代表当前的数字，第二个元素代表出现的次数，根据出现次数倒序排列
        PriorityQueue<int[]> queue = new PriorityQueue<>((int[] n1, int[] n2) -> n1[1] - n2[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num = entry.getKey();
            int count = entry.getValue();
            if(queue.size() == k){ //当堆的长度达到了前k个，此时就是前k个高频元素
                if(queue.peek()[1] < count){  //再进来一个数，就去比较这个数字的出现次数，和小根堆堆顶的数字(当前出现最少的数字)出现次数谁多，如果多就替换，
                    queue.poll();
                    queue.offer(new int[] {num, count});
                }
            }else{ //如果堆的长度还没达到前k个，就把这个新进来的加进去
                queue.offer(new int[]{num, count});
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }
        return res;
    }

原文地址：http://www.cnblogs.com/phonk/p/16817324.html