TopK 问题

技术文章 3个月前 完美者
1,156 0

标签:index   int   元素   最大   大于   数据   creat   治法   顺序   

最近面试时遇到这个问题,蛮有意思的,经典题目了。

问题如下:

   在一堆数据里面找到前 K 大(当然也可以是前 K 小)的数。

1、首先想到的对数据进行全排序,取出其中最大的K个数。比如:快排或者归并

后期补代码吧

2、其次做一些优化,其实找前K大的不用全部所有值得顺序都确定好,只要排K个值就好了,故想了下,有这个部分排序算法,比如:冒泡

手写一波:

func MaoPao(arr []int, k int) []int {
	if k > len(arr) {
		return arr
	}
	for i := 0; i < k; i++ {
		for j := 0; j < len(arr)-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = Swap(arr[j], arr[j+1])
			}

		}
	}
	return arr[len(arr)-k:]
}

  

3、更进一步,我们只找最大的K个元素,不排序,直接上堆。

 

建立小根堆,用于存储当前最大的k个元素,从k+1开始,和堆顶(堆中最小)元素比较,若被扫描的元素大于堆顶,替换堆顶的元素,

并调整堆,保证堆内的k个元素,总是当前最大的k个元素。直到扫描完全部数据。即可得到topk元素。

堆的变化有点意思哈:

func TopKByMinHeap(nums []int, k int) []int {
	length := len(nums)
	if length < k {
		return nums
	}
	minHeap := make([]int, 0)
	minHeap = append(minHeap, nums[:k]...)
	CreateMinHeap(minHeap)
	for i := k; i < length; i++ {
		if nums[i] > minHeap[0] {
			minHeap[0] = nums[i]
			MinHeapify(minHeap, 0, k)
		}
	}
	return minHeap
}

// 自底向上创建小根堆
func CreateMinHeap(nums []int) {
	length := len(nums)
	for i := length - 1; i >= 0; i-- {
		MinHeapify(nums, i, length)
	}
}

// 维护小根堆
func MinHeapify(nums []int, posIndex, length int) {
	leftIndex := 2*posIndex + 1
	rightIndex := 2*posIndex + 2
	minIndex := posIndex
	// 左孩子存在并且小于当前节点值时,最小值index替换为左孩子index
	if leftIndex < length && nums[leftIndex] < nums[minIndex] {
		minIndex = leftIndex
	}
	// 右孩子存在并且小于当前节点值时,最小值index替换为右孩子index
	if rightIndex < length && nums[rightIndex] < nums[minIndex] {
		minIndex = rightIndex
	}
	// 最小值结点index不等于当前结点时,替换为当前节点和其中较小孩子结点
	if minIndex != posIndex {
		nums[posIndex], nums[minIndex] = nums[minIndex], nums[posIndex]
		MinHeapify(nums, minIndex, length)
	}
}

4、后续可能使用快排的减治法进行,未完待续。。。

 

TopK 问题

标签:index   int   元素   最大   大于   数据   creat   治法   顺序   

原文地址:https://www.cnblogs.com/lvpengbo/p/14182270.html

版权声明:完美者 发表于 2020-12-29 11:53:03。
转载请注明:TopK 问题 | 完美导航

暂无评论

暂无评论...