刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

思路

建大顶堆与堆排序不同，元素并非完全递减，所以这里只需重复k-1次建堆过程，然后此时的堆顶nums[0]即是所找的第k大的值

• 注意边界思考
• 建堆过程可以打开注释观察

代码

func findKthLargest(nums []int, k int) int {
	heapSize := len(nums)
	buildMaxHeap(nums, heapSize)
	// fmt.Printf("nowHeap nums: %v\n", nums)
	// 做k-1次调整即可在栈顶得到第k大的数，此时坐标下限为(len(nums)-1) - (k-1)，边界关系不可到达此值，所以判断条件为大于号
	for i := len(nums) - 1; i > (len(nums)-1)-(k-1); i-- {
		nums[0], nums[i] = nums[i], nums[0]
		// fmt.Printf("nowHeap nums: %v\n", nums)
		heapSize--
		maxHeapify(nums, 0, heapSize)
	}
	return nums[0]
}

func buildMaxHeap(a []int, heapSize int) {
	for i := heapSize / 2; i >= 0; i-- {
		maxHeapify(a, i, heapSize)
	}
}

func maxHeapify(a []int, i, heapSize int) {
	// fmt.Printf("func: maxHeapify(nums, %v, %v)\n", i, heapSize)
	l, r, largest := i*2+1, i*2+2, i
	if l < heapSize && a[l] > a[largest] {
		largest = l
	}
	if r < heapSize && a[r] > a[largest] {
		largest = r
	}
	if largest != i {
		a[i], a[largest] = a[largest], a[i]
        // fmt.Printf("nowHeap nums: %v\n", nums)
		maxHeapify(a, largest, heapSize)
	}
}