题解 | #最小的K个数#

最小的K个数

https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf

//利用golang中collector的包装的heap的push和pop算法
package main

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 *
 * @param input int整型一维数组
 * @param k int整型
 * @return int整型一维数组
 */
import (
	"container/heap"
)
// 实现一个int的heap
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] } //实现一个最大堆
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

// Push 往堆中插入一个元素
func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

// Pop 从堆中弹出最大的元素
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	*h = old[0 : n-1]
	x := old[n-1]
	return x
}

func (h *IntHeap) ConvertToInt() []int {
	old := *h
	return old
}

func GetLeastNumbers_Solution(input []int, k int) []int {
	// write code here
	if k > len(input) {
		return input
	}
	if k == 0 {
		return []int{}
	}
	topK := &IntHeap{}
	heap.Init(topK)
	for i := 0; i < k; i++ {
		heap.Push(topK, input[i])
	}

	//后面的元素替换堆中存储的最大元素
	for i := k; i < len(input); i++ {
		tmp := heap.Pop(topK).(int)
		if tmp > input[i] {
			heap.Push(topK, input[i])
		} else {
			heap.Push(topK, tmp)
		}
	}
	return topK.ConvertToInt()
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 13:35
虽然不怎么光彩,经过这件事,可能我真的要去认同“面试八股文早该淘汰!不会用AI作弊的程序员=新时代文盲!”这句话了
HellowordX:Ai的出现是解放劳动力的,不是用来破坏公平竞争环境的,这样下去,轻则取消所有线上面试,严重了会影响整个行业对所有人产生影响,企业会拉高入职考核各种离谱考核会层出不穷
你找工作的时候用AI吗?
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务