关于堆:LeetCode刷题日记之前K个高频元素

前 K 个高频元素，这是一个很有代表性的问题，在理论生存中的利用场景其实也很多，比方微博里每天统计实时热点信息等。

先看下题：

给你一个整数数组 nums 和一个整数 k，请你返回其中呈现频率前 k 高的元素。你能够按 任意程序 返回答案。

示例 1:

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

进阶：你所设计算法的工夫复杂度 必须 优于 O(n log n)，其中 n 是数组大小。

<!–more–>

这道题的进阶要求工夫复杂度要优于 O(nlogn)，那个别的快排，归并等就能够摈弃了。

而对于 logn 这个工夫复杂度咱们能很疾速的联想到二分，二叉搜寻树和堆。前两个想了下本场景实用不了。

使用堆

因而咱们来推导下堆是否能够小于 O(nlogn)？答案是必定的，堆能够在 O(nlogk)(k<n)的工夫复杂度下等到后果.

桶排序

那除了堆，咱们还有其余方法解决么？当然是有的，那就是桶排序。

思路

咱们来理一下为什么能够用堆和桶排序两种实现失去答案。我的推导过程如下，大家能够当做参考，有好的计划也欢送和我探讨。

首先要统计前 k 个高频元素，咱们必须至多要将整个数组遍历一次。这个咱们很快就想到 Map 去记录每个元素呈现的次数，这个在 字母异位词 那题外面做过。

而后须要去从 Map 外面的 value 进行排序，排序后从大到小的前 k 个元素就是后果。而造成解法差别就是在排序的实现上。

你能够是各种排序，快排，归并，插入，桶，冒泡，希尔，堆排序等，而各种排序的工夫复杂度决定了最初的工夫复杂度。

而后因为在各个排序里小于进阶要求 O(nlogn)的就只有堆排序的 O(nlogk)和桶排序的 O(n).

具体实现

堆

法一

int[] topK = new int[k];
Map<Integer, Integer> countMap = new HashMap<>();
// 第一个为数组值，第二个为呈现次数
PriorityQueue<int[]> priQueue = new PriorityQueue<>((o1,o2)->(o2[1]-o1[1]));

for (int num : nums) {countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}

for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {int value = entry.getKey(), count = entry.getValue();

    priQueue.offer(new int[]{value, count});
}

for (int i = 0; i < k; i++) {topK[i] = priQueue.poll()[0];
}

return topK;

这个是我一开始写的一种谬误的写法，应该是初学者比拟容易犯的谬误。这个解法的工夫复杂度是 O(nlogn)而不是 O(nlogk)，至于为什么，看下一个解法我会阐明。而且这外面 PriorityQueue 的泛型类型用的是 int[]，这个写的其实还是有点不优雅的，没必要新开构造去记录，间接用现有的Map.Entry<Integer,Integer> 即可。

法二

int[] topK = new int[k];
Map<Integer, Integer> countMap = new HashMap<>();
// 第一个为数组值，第二个为呈现次数
PriorityQueue<int[]> priQueue = new PriorityQueue<>((o1,o2)->(o1[1]-o2[1]));

for (int num : nums) {countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}

for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {int value = entry.getKey(), count = entry.getValue();

    // 始终保持堆里只有 k 个元素，这样 logk 速度会快点
    if (priQueue.size() < k) {priQueue.offer(new int[]{value, count});
    } else {if (priQueue.peek()[1] < count) {priQueue.poll();
            priQueue.offer(new int[]{value, count});
        }
    }
}

for (int i = 0; i < k; i++) {topK[i] = priQueue.poll()[0];
}

return topK;

法二和法一的区别在于，法一是构建大顶堆，将 n 个元素都装进堆 PriorityQueue 中，这样整个建堆的工夫复杂度是 O(nlogn)，而法二是构建小顶堆，而后放弃堆外面的元素始终只有 k 个，大于 k 个会先将堆顶元素出堆在将其余元素入堆。

对于在 O(nlogk)的复杂度到底用大顶堆还是小顶堆是怎么确定的呢？我是这么记得，如果是要失去前 k 大的数，那就要构建小顶堆，而后一直将大于堆顶的数放进小顶堆，最初堆里剩下的就是最大的 k 个数了；反之亦然。

法三

if (nums.length == 0 || nums.length < k) {return new int[]{};}

Map<Integer, Integer> numsMap = new HashMap<>();
for (int num : nums) {numsMap.put(num, numsMap.getOrDefault(num, 0) + 1);
}

PriorityQueue<Map.Entry<Integer, Integer>> pri = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());
for (Map.Entry<Integer, Integer> num : numsMap.entrySet()) {if (pri.size() < k) {pri.offer(num);
    } else if (pri.peek().getValue() < num.getValue()) {pri.poll();
        pri.offer(num);
    }
}

int[] res = new int[k];
for (int i = 0; i < k; i++) {res[i] = pri.poll().getKey();
}


return res;

法三是 Map.Entry<Integer,Integer> 实现，这样代码会简洁很多，可读性好很多。

上面发四是从其余中央看到的实现办法，看看和法三有什么不同呢？

我一开始看到也想了一会才发现实现思路。

法四

Map<Integer, Integer> map = new HashMap();
for(int n : nums) {int freq = map.getOrDefault(n, 0) + 1;
    map.put(n, freq);
}
// 这里是间接将 map 的 entry 做比拟，这样就能有多个元素了，不必新建数组或者实体类
Queue<Map.Entry<Integer,Integer>> heap = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
/**
 * 这里也是保护一个小根堆，然而这里思路和失常有点区别，失常思路是会在 k 个元素满之后判断元素是否比堆顶大，而后出堆入堆，* 这里实现有点不一样，是先入堆，而后在出堆堆顶元素，这里工夫复杂度是 O(nlog(k+1))，实践上说应该比 O(nlogk)慢，*/
for(Map.Entry<Integer,Integer> entry: map.entrySet()) {heap.offer(entry);
    if(heap.size() > k) {heap.poll();
    }
}
int[] res = new int[k];
for(int i = 0; i < k; i++) {res[i] = heap.poll().getKey();
}
return res;

这里的工夫复杂度严格来说是 O(nlog(k+1))，因为堆里会有 k + 1 个元素，当检测到元素大于 k 会将堆顶最小元素出堆而后在入堆，这样省略了比拟过程，然而工夫复杂度高了点，在对性能要求不那么严格的时候也能够这种解法。

桶排序

桶排序的思路是会用 1 -nums.length 这么多个桶，而后遍历整个 Map，把 Map 的 Entry 放进 value 的桶里，这时候一个桶可能有多个元素，而后顺次从大到小将元素取出来即可。

这里我一开始想的比较简单间接用一个数组代替一个桶，这样是不行的，桶可能会有多个元素，会存在笼罩的状况，之后再计数排序的场景能够用数组代替桶。

Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}

// 不能间接用数组记录，因为会存在多个数字呈现次数一样，这种用数组会被笼罩
// 因而间接在每个数组地位放一个 list。// 桶的含意是每个呈现次数蕴含的数字，桶里的元素是多个
// 一个桶里会蕴含所有呈现次数为该桶下标的数字
List<Integer>[] tong = new ArrayList[nums.length + 1];
for (Map.Entry<Integer, Integer> num : countMap.entrySet()) {if (tong[num.getValue()]==null) tong[num.getValue()] = new ArrayList<>();
    tong[num.getValue()].add(num.getKey());
}

int[] res = new int[k];
int index = 0;
// 因为数组元素赋值是到了 nums.length, 因而是从 nums.length 而不是 nums.length-1
for (int i = nums.length; i >= 0; i--) {if (tong[i] == null) continue;
    for (int n : tong[i]) {res[index++] = n;
        if (index == k) return res;
    }
}

return res;

写在最初

咱们在做题的时候不要仅仅谋求做进去，而要把所有可能的解法都试试，而后比拟优劣，对于一些速度比较慢的解法，看看是否能优化将其效率进步。

有的时候你将一个算法的效率晋升了十倍乃至几十倍，那种成就感是空前的！

享受这种过程，你前面写出的有“坏滋味”的代码会越来越少。