输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
示例 1:
输入:arr = [3,2,1], k = 2 输出:[1,2] 或者 [2,1] 示例 2:
输入:arr = [0,1,2,1], k = 1 输出:[0]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
TopK问题,只需维护一个大小为k的堆即可,题目要求找出最小的k个数,因此需要维护一个大小为k的大顶堆,堆顶元素为第k小的数,当新来的值小于堆顶元素时就替换掉堆顶元素并进行堆调整(shiftdown
),由于输出的结果是升序排序的,因此还需要对堆数组进行排序,可以使用堆排序也可以使用其它排序方法。
class Solution {
private int maxHeap[], size;
public int[] getLeastNumbers(int[] arr, int k) {
maxHeap = new int[k];
if (k == 0)
return maxHeap;
size = k;
for (int i = 0; i < k; i++) {
maxHeap[i] = arr[i];
}
for (int i = size / 2 - 1; i >= 0; i--) {
shiftdown(i);
}
for (int i = k; i < arr.length; i++) {
if (arr[i] < maxHeap[0]) {
maxHeap[0] = arr[i];
shiftdown(0);
}
}
int res[] = new int[k];
res[k - 1] = maxHeap[0];
for (int i = k - 1; i > 0; i--) {
maxHeap[0] = maxHeap[i];
size--;
shiftdown(0);
res[i - 1] = maxHeap[0];
}
return res;
}
public void shiftdown(int ind) {
int left_child = 2 * ind + 1;
int right_child = 2 * ind + 2;
int large_ind = ind;
if (left_child < size && maxHeap[large_ind] < maxHeap[left_child]) {
large_ind = left_child;
}
if (right_child < size && maxHeap[large_ind] < maxHeap[right_child]) {
large_ind = right_child;
}
if (large_ind != ind) {
int temp = maxHeap[large_ind];
maxHeap[large_ind] = maxHeap[ind];
maxHeap[ind] = temp;
shiftdown(large_ind);
}
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)