目录
寻找第K大
访问量:452



一、简介

有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。


给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。

要求:时间复杂度 O(nlogn)O(nlogn),空间复杂度 O(1)O(1)


示例1

输入:[1,3,5,2,2],5,3

返回值 2


示例1

输入:[10,10,9,9,8,7,5,6,4,3,4,2],12,3

返回值 9


二、解法

/**
 * 思路: 使用最大的 k个数字,构建一个最小堆,那么堆顶元素,即第k大的数字
 * @param a int整型一维数组
 * @param n int整型
 * @param K int整型
 * @return int整型
 */
func findKth( a []int ,  n int ,  K int ) int {
	// write code here
    // 先使用前K个元素,构建一个最小堆
	heap := a[:K]

	// 将 heap 调整为 最小堆
	for index := K/2 - 1; index >=0; index -- {
		jumpMinHeap(heap, index)
	}

	// 将剩下的元素依次插入堆中
	if n > K {
		for index := K; index < n; index ++ {
			// 如果当前节点,小于等于堆顶元素,直接丢弃
			if a[index] <= heap[0] {
				continue
			}
			
			// 替换堆定元素,再次调整
			heap[0] = a[index]
			jumpMinHeap(heap, 0)
		} 
	}
	
	// 返回堆顶元素
	return heap[0]
}

/**
 * @param data 需要调整的堆
 * @param index 需要调整的节点
 */
func jumpMinHeap(data []int, index int)  {
	leftIndex := index *2 + 1
	rightIndex := index*2 + 2
	
	// 无左右节点
	if leftIndex >= len(data) {
		return
	}
	
	// 无右节点
	if rightIndex >= len(data) {
		if data[leftIndex] >= data[index] {
			return
		}
		
		// 交换 左节点 和 根节点
		data[leftIndex], data[index] =  data[index], data[leftIndex]
		
		// 因当前节点,无右节点,左和根节点交换后,不需要再递归比较
		return
	}
	
	// 根节点已是最小值,不需要再次比较
	if data[index] <= data[leftIndex] && data[index] <= data[rightIndex] {
		return
	}
	
	// 左节点是最小值
	if data[leftIndex] < data[index] && data[leftIndex] <= data[rightIndex] {
		// 交换 左节点 和 根节点
		data[leftIndex], data[index] =  data[index], data[leftIndex]
		
		// 继续递归 左节点
		jumpMinHeap(data, leftIndex)
		return
	}
	
	// 如果右节点是最小值
	if data[rightIndex] < data[index] && data[rightIndex] < data[leftIndex] {
		// 交换 左节点 和 根节点
		data[rightIndex], data[index] =  data[index], data[rightIndex]

		// 继续递归 左节点
		jumpMinHeap(data, rightIndex)
		return
	}
}



题目来源:牛客