11.堆
一.最小的k个数
1.题目描述：
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
2.示例：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
3.解:
（1）我的答案：
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(k<=0 || k>arr.length) return new int[0];
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((x, y) -> (y - x));
for (int ele : arr) {
if (priorityQueue.size() < k) priorityQueue.offer(ele);
else if (priorityQueue.peek() > ele) {
priorityQueue.poll();
priorityQueue.offer(ele);
}
}
int[] res = new int[priorityQueue.size()];
int index = 0;
for (int ele :priorityQueue) res[index++] = ele;
return res;
}
}（2）网友答案：
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 默认是小根堆，实现大根堆需要重写一下比较器。
Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
for (int num: arr) {
if (pq.size() < k) {
pq.offer(num);
} else if (num < pq.peek()) {
pq.poll();
pq.offer(num);
}
}
// 返回堆中的元素
int[] res = new int[pq.size()];
int idx = 0;
for(int num: pq) {
res[idx++] = num;
}
return res;
}
}4.总结
堆其实就是用一维数组形式存储的一颗二叉树，其中每一个节点的值都大于/小于它的子节点。java中使用优先队列这种数据结构来存储堆，并且默认是小根堆（根节点是最小值的堆），本题用堆的方式解题的话，需要的是尺寸为k的大根堆，这样就可以保证这k个数字是arr里最小的几个。
二.最后一块石头的重量
1.题目描述：
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
2.示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
3.解:
（1）我的答案：
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((x, y) -> (y - x));
for (int ele : stones) priorityQueue.offer(ele);
while (priorityQueue.size() > 1) {
int a = priorityQueue.poll();
int b = priorityQueue.poll();
if (a != b) priorityQueue.offer(Math.abs(a - b));
}
if (priorityQueue.size() == 1) return priorityQueue.peek();
return 0;
}
}（2）网友答案：
class Solution {
int size = 0;
int[] nums;
public int lastStoneWeight(int[] stones) {
nums = new int[stones.length];
for(int n : stones){
insert(n);
}
while(size > 1){
int x = pop();
int y = pop();
if(x != y){
insert(Math.abs(x - y));
}
}
return size == 0 ? 0 : nums[0];
}
public void insert(int data){
nums[size++] = data;
int father = size / 2, child = size;
while (father > 0){
if(nums[father - 1] < data){
int temp = nums[father - 1];
nums[father - 1] = data;
nums[child - 1] = temp;
child = father;
father /= 2;
} else{
break;
}
}
}
public int pop(){
int res = nums[0];
nums[0] = nums[--size];
int father = 0;
while (father < size){
int left = 2 * father + 1, right = 2 * father + 2;
if(left < size){
int max = left;
if(right < size && nums[left] < nums[right]) max = right;
if(nums[father] < nums[max]){
int temp = nums[father];
nums[father] = nums[max];
nums[max] = temp;
father = max;
} else {
break;
}
} else{
break;
}
}
return res;
}
}4.总结
网友的答案将poll方法和offer方法自己写了一遍，注意读懂代码，理解其中的原理。poll方法记住两点：1.头和尾交换值，然后从头开始和左右节点中的最大值比较，满足条件则交换值，如此遍历至队尾。2.记住在一维数组中怎么根据父节点的坐标表示两个字节的的坐标。offer方法记住两点：1.数组结尾插入新的值，然后从尾开始找父节点比较值，满足条件则交换值，如此遍历至根节点。2.记住在一维数组中怎么根据子节点坐标表示父节点的坐标。
三.数据流中的第 K 大元素
1.题目描述：
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
2.示例：
输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]
解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
1 <= k <= 104
0 <= nums.length <= 104
-104 <= nums[i] <= 104
-104 <= val <= 104
最多调用 add 方法 104 次
题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素
3.解:
class KthLargest {
private int k;
private PriorityQueue<Integer> pg;
public KthLargest(int k, int[] nums) {
this.k = k;
pg = new PriorityQueue<>(k);
for (int ele : nums) add(ele);
}
public int add(int val) {
if (pg.size() < k) {
pg.offer(val);
}
else if (pg.peek() < val) {
pg.poll();
pg.offer(val);
}
return pg.peek();
}
}4.总结
自己写出来的，没什么可说的，只要注意初始化pg的时候记得先指定大小，可以减少一点执行时间和占用的内存。
四.第 k 个数
1.题目描述：
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
2.示例：
输入: k = 5
输出: 9
3.解:
import java.util.*;
class Solution {
public int getKthMagicNumber(int k) {
// 最小堆处理写入数值 试了Integer不够
PriorityQueue<Long> PriorityQueue = new PriorityQueue<>();
// HashSet 保存k个位数值
Set<Long> list = new HashSet<>();
PriorityQueue.add(1L);
while ( true ) {
// 获取并删除队首元素
Long val = PriorityQueue.poll();
// 该元素是否已在HashSet中，在将不操作，否则插入
if ( !list.contains(val) ) {
list.add(val);
PriorityQueue.add( val * 3 );
PriorityQueue.add( val * 5 );
PriorityQueue.add( val * 7 );
}
// 返回第k个位数值
if ( list.size() == k ) {
return val.intValue();
}
}
}
//
public static void main(String[] args){
int res = (new Solution()).getKthMagicNumber(643);
System.out.println(res);
}
}4.总结
用最小堆的堆顶元素最小和哈希集的去重功能来实现：每次循环，从堆中取出并删除堆顶最小值，哈希集中不存在则添加到哈希集中，然后该值分别乘以3，5，7，并加入堆中。循环多次直到哈希集的长度刚好为k，则第k个数就是结果。
投递腾讯云智研发等公司7个岗位