一、简介

有一个整数数组，请你根据快速排序的思路，找出数组中第 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
	}
}

题目来源：牛客