215.M 数组中的第K个最大元素

Problem: 215. 数组中的第K个最大元素

思路

先构造一个大根堆，此时根节点是最大元素，此时再做k-1次删除根节点的操作，然后根节点就是第k大的元素

Code

func findKthLargest(nums []int, k int) int {
	for i := len(nums)/2 - 1; i >= 0; i-- {
		maxHeapify(nums, i, len(nums))
	}

	heapSize := len(nums)
	// 第k-1大的元素应该是交换至位置len(nums)-(k-1)
	for i := len(nums) - 1; i >= len(nums)-k+1; i-- {
		nums[0], nums[i] = nums[i], nums[0]
		heapSize--
		maxHeapify(nums, 0, heapSize)
	}

	return nums[0]
}

func maxHeapify(nums []int, root int, heapSize int) {
	l, r, largest := 2*root+1, 2*root+2, root
	if l < heapSize && nums[l] > nums[largest] {
		largest = l
	}

	if r < heapSize && nums[r] > nums[largest] {
		largest = r
	}

	if largest != root {
		nums[root], nums[largest] = nums[largest], nums[root]
		maxHeapify(nums, largest, heapSize)
	}
}