https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=295&tqId=23263&ru=%2Fpractice%2F253d2c59ec3e4bc68da16833f79a38e4&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
思路： 构建最小堆，依次取出前k个。 构建最小堆的时候每次插入元素后要向上调整，取出最小元素后要向下调整。
package main
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param input int整型一维数组 * @param k int整型 * @return int整型一维数组 */
var index int
func adjustHeap(arr []int, len int) {
for i := (len - 1) / 2; i >= 0; { if arr[i] > arr[len] { tmp := arr[i] arr[i] = arr[len] arr[len] = tmp len = i if i == 0 { break } i = (i - 1) / 2 } else { break } } }
func top(arr []int) int { result := arr[0] arr[0] = arr[index] arr[index] = 2000 index-- //从上往下调整 i := 0 for arr[i] >= 0 { if arr[i*2+1] > 1000 { break } if arr[i*2+1] <= arr[i*2+2] && arr[i] > arr[i*2+1] { tmp := arr[i] arr[i] = arr[i*2+1] arr[i*2+1] = tmp i = i*2 + 1 continue } if arr[i*2+1] > arr[i*2+2] && arr[i] > arr[i*2+2] { tmp := arr[i] arr[i] = arr[i*2+2] arr[i*2+2] = tmp i = i*2 + 2 continue } break }
return result
} func GetLeastNumbers_Solution(input []int, k int) []int { // write code here result := make([]int, 0)
if k == 0 || len(input) == 0 { return result } if k > len(input) { return input }
heapSize := 2*len(input) + 1
minHeap := make([]int, heapSize) for i := 0; i < len(minHeap); i++ { minHeap[i] = 2000 } minHeap[0] = input[0] //构建最小堆 for i := 1; i < len(input); i++ { minHeap[i] = input[i] adjustHeap(minHeap, i) }
index = len(input) - 1 //取出前k个最小值 for i := 0; i < k; i++ { result = append(result, top(minHeap)) } return result } 标签：arr,int,个数,BM46,len,最小,result,minHeap,input From： https://www.cnblogs.com/starter-songudi/p/17085668.html