面试题 17.14. 最小K个数 发表于 2021-04-08 | 分类于 leetcode 堆栈的题目还真是两级分化 用时 :10min 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778const swap = function (arr,i,j) { [arr[i],arr[j]] = [arr[j],arr[i]]}class MaxHeap { constructor() { this.count = 0 this.data = new Array(this.count + 1) } shiftUp(k) { // 把新的元素往上排 while(k>=1) { let father = Math.floor(k / 2) if (this.data[k] > this.data[father]) { swap(this.data,k,father) k = father } else { break } } } shiftDown(k) { while( k * 2 <= this.count) { // 表示k 有孩子 let j = k if (k * 2 + 1 <= this.count && this.data[k * 2 + 1] > this.data[k] && this.data[k * 2 + 1] > this.data[k * 2]) { j = k * 2 + 1 } else if (this.data[k * 2] > this.data[k]) { j = k * 2 } else { break } swap(this.data,j,k) k = j } } size() { return this.count } isEmpty() { return this.count === 0 } insert(item) { this.data[++this.count] = item this.shiftUp(this.count) } extractMax() { if (this.count < 0) return let ret = this.data[1] swap(this.data,1,this.count--) this.shiftDown(1) return ret } top() { return this.data[1] }}var smallestK = function(arr, k) { var heap = new MaxHeap() var K = 0 while(K < k) { heap.insert(arr[K]) K++ } // 将堆维持在K的大小 while(K < arr.length) { var max = heap.top() if (arr[K] < max) { heap.extractMax() heap.insert(arr[K]) } K++ } var size = heap.size() return heap.data.slice(1, 1 + size )};