网络异常，图片无法展示
|
输入整数数组 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] 复制代码
限制：
0 <= k <= arr.length <= 100000 <= arr[i] <= 10000
本题很简单，所以我们话不多说，直接看题解
题解1：排序&截取
首先直接一手 sort 排序，然后 slice 截取前k 个元素即可
代码如下：
var getLeastNumbers = function(arr, k) { arr.sort((a,b) => a-b); return arr.slice(0,k); } 复制代码
题解2：大顶堆维护前 k 个最小值
- 因为要维护前
k个最小值，所以呢，首先需要写一个大顶堆，这样每次有比堆顶元素更小的值就插入堆中，然后弹出堆顶元素 - 创建大顶堆实例，循环数组中元素，当堆中数量不够
k个或者当前值比堆顶元素小的时候，将当前值插入堆中
代码如下：
// 创建大顶堆类 class BigHeap { constructor(k){ this.arr = []; this.size = 0; this.max = k; } // 插入操作 push(val){ this.arr.push(val); this.size++; if(this.size>1){ let cur = this.size-1, parent = (cur-1)>>1; while(cur>0&&this.arr[cur]>this.arr[parent]){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent,parent = (cur-1)>>1; } } if(this.size>this.max) this.pop(); } // 弹出操作 pop(){ this.arr[0] = this.arr.pop(); this.size--; let cur = 0, childl = 1,childr = 2; while( (childl<this.size&&this.arr[childl]>this.arr[cur]) || (childr<this.size&&this.arr[childr]>this.arr[cur]) ){ if(childr<this.size&&this.arr[childr]>this.arr[childl]){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr; }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]] cur = childl; } childl = cur*2+1,childr = cur*2+2; } } // 获取堆顶元素 top(){ return this.arr[0] } } var getLeastNumbers = function(arr, k) { // 特判k=0 if(k===0) return []; // 创建大顶堆实例 const heap = new BigHeap(k); // 循环数组元素 for(let i = 0;i<arr.length;i++){ if(heap.size<k||arr[i]<heap.top()) heap.push(arr[i]) } // 返回堆中保存的k个数字 return heap.arr; }; 复制代码
至此我们就完成了 leetcode-剑指 Offer 40-最小的k个数
如有任何问题或建议，欢迎留言讨论！
