获取数组中最小的k个数字_29
思路：利用小根堆 面试或者其他啥情况估计是不允许大家直接用优先级队列的，所以我们还是老老实实的实现一个堆结构吧； 关于堆的结构以及其相应实现大家可以看我之前的一个笔记https://www.jianshu.com/writer#/notebooks/40413732/notes/55370532
我们这里和普通堆排序和堆数据修改有一点区别，那就是这里我们需要先实现一个小根堆，然后每一次拿第一个数据然后把这个数据删掉，但是我们这里存在一个问题，数组不太好删数据，删除的话要进行一个所有数据的前移，因此， 我这里取了个巧，我把第一个数字和最后一个数字交换，然后我当这个数组的长度减了1，当最后一个数字不存在，然后会进行一个从顶到下的重建，同理第二大的数字出来后与倒数第二个交换，当倒数第二个数就不存在了，以此类推。。。
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (k>input.length){
return res;
}
//插入实现小根堆
for (int i = 0; i < input.length; i++) {
heapInsert(input, i);
}
for (int i = 0; i < k; i++) {
res.add(input[0]);
swap(input,0,input.length-1-i);
heapify(input,0,input.length-i-1);
}
return res;
}
@Test
public void test(){
ArrayList<Integer> integers = GetLeastNumbers_Solution(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 10);
integers.forEach(item->{
System.out.print(item+" ");
});
}
//插入实现小根堆
public void heapInsert(int[] heapArr, int currIndex) {
while (heapArr[currIndex] < heapArr[parentIndex(currIndex)]) {
swap(heapArr, currIndex, parentIndex(currIndex));
currIndex = parentIndex(currIndex);
}
}
/**
* 堆平衡
* 当某个节点发送变化了,那么其子树就需要重新维持平衡
* param 堆,修改位置,堆数组大小
*/
public void heapify(int[] heapArr, int index, int heapArrSize) {
//如果存在左孩子节点
while (leftChild(index) < heapArrSize) {
//左右孩子节点最大的值;
int miniIndex = rightChild(index) < heapArrSize && heapArr[rightChild(index)] < heapArr[leftChild(index)] ?
rightChild(index) : leftChild(index);
if (heapArr[miniIndex] < heapArr[index]) {
swap(heapArr, index, miniIndex);
index = miniIndex;
} else {
break;
}
}
}
private void swap(int[] heapArr, int currIndex, int parentIndex) {
int temp = heapArr[currIndex];
heapArr[currIndex] = heapArr[parentIndex];
heapArr[parentIndex] = temp;
}
public int parentIndex(int childIndex) {
return (childIndex - 1) / 2;
}
public int leftChild(int parentIndex) {
return 2 * parentIndex + 1;
}
public int rightChild(int parentIndex) {
return 2 * parentIndex + 2;
}同理这里也把拿最大的k个数实现了（利用大根堆）
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (k>input.length){
return res;
}
//插入实现大根堆
for (int i = 0; i < input.length; i++) {
heapInsert(input, i);
}
for (int i = 0; i < k; i++) {
res.add(input[0]);
swap(input,0,input.length-1-i);
heapify(input,0,input.length-i-1);
}
return res;
}
@Test
public void test(){
ArrayList<Integer> integers = GetLeastNumbers_Solution(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 10);
integers.forEach(item->{
System.out.print(item+" ");
});
}
//插入实现大根堆
public void heapInsert(int[] heapArr, int currIndex) {
while (heapArr[currIndex] > heapArr[parentIndex(currIndex)]) {
swap(heapArr, currIndex, parentIndex(currIndex));
currIndex = parentIndex(currIndex);
}
}
/**
* 堆平衡
* 当某个节点发送变化了,那么其子树就需要重新维持平衡
* param 堆,修改位置,堆数组大小
*/
public void heapify(int[] heapArr, int index, int heapArrSize) {
//如果存在左孩子节点
while (leftChild(index) < heapArrSize) {
//左右孩子节点最大的值;
int largestIndex = rightChild(index) < heapArrSize && heapArr[rightChild(index)] > heapArr[leftChild(index)] ?
rightChild(index) : leftChild(index);
if (heapArr[largestIndex] > heapArr[index]) {
swap(heapArr, index, largestIndex);
index = largestIndex;
} else {
break;
}
}
}
private void swap(int[] heapArr, int currIndex, int parentIndex) {
int temp = heapArr[currIndex];
heapArr[currIndex] = heapArr[parentIndex];
heapArr[parentIndex] = temp;
}
public int parentIndex(int childIndex) {
return (childIndex - 1) / 2;
}
public int leftChild(int parentIndex) {
return 2 * parentIndex + 1;
}
public int rightChild(int parentIndex) {
return 2 * parentIndex + 2;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/4/22 下，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
