每日一题 --- 数组中的第 K 个最大元素[力扣][Go]

数组中的第 K 个最大元素

题目：数组中的第 K 个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 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 <= 104
-104 <= nums[i] <= 104

方法一：

使用快速排序，排好序后找到第K大的元素。

func findKthLargest(nums []int, k int) int {if len(nums) < k {return -1}qSort(nums)return nums[len(nums)-k]
}func qSort(nums []int) {quickSort(nums, 0, len(nums)-1)
}// 快速排序算法
func quickSort(nums []int, min, max int) {if min < max {pos := partition(nums, min, max)quickSort(nums, min, pos-1)quickSort(nums, pos+1, max)}
}func partition(nums []int, l, r int) int {base := nums[l]for l < r {for l < r && nums[r] >= base {r--}nums[l] = nums[r]for l < r && nums[l] <= base {l++}nums[r] = nums[l]}nums[l] = basereturn l
}

方法二：

使用堆排序，排好序后，调整K次大根堆，然后取出元素值

func findKthLargest(nums []int, k int) int {// 实现卫兵nums = append([]int{0}, nums...)Len := len(nums)buildMaxHeap(nums, Len-1)for i := Len - 1; i >= Len-k; i-- {nums[1], nums[i] = nums[i], nums[1]maxHeapAdjust(nums, 1, i-1)}return nums[Len-k]
}// 建堆
func buildMaxHeap(nums []int, len int) {for i := len / 2; i > 0; i-- {maxHeapAdjust(nums, i, len)}
}// 调整堆, k为根元素，从k开始往下调整
func maxHeapAdjust(nums []int, k, len int) {nums[0] = nums[k]for i := 2 * k; i <= len; i *= 2 {if i < len && nums[i] < nums[i+1] {i++}if nums[i] <= nums[0] {break} else {nums[k] = nums[i]k = i}}nums[k] = nums[0]
}

方法一和方法二都是采取，先排序再取值的办法。时间复杂度为O(n*log n)。

其实我们可以改进下方法一：利用分治思想将时间复杂度期望降至O(1)。

具体思想讲解：4.3分治寻找第k小元素_哔哩哔哩_bilibili

在这里插入图片描述

方法三：

分治法，与上面思想不同的是，我们不执着于找中位数，而是采用随机分治，当随机到的基数正好为第K大时，直接返回。详细讲解参考力扣题解部分。

func findKthLargest(nums []int, k int) int {if len(nums) < k {return -1}return qSort(nums, len(nums)-k)
}func qSort(nums []int, index int) int {rand.Seed(time.Now().UnixNano())return quickSort(nums, 0, len(nums)-1, index)
}// 快速排序算法
func quickSort(nums []int, min, max, index int) int {randN := rand.Int()%(max-min+1) + minpos := partition(nums, min, max, randN)if pos == index {return nums[pos]} else if pos < index {return quickSort(nums, pos+1, max, index)} else {return quickSort(nums, min, pos-1, index)}}func partition(nums []int, l, r, random int) int {nums[random], nums[l] = nums[l], nums[random]base := nums[l]for l < r {for l < r && nums[r] >= base {r--}nums[l] = nums[r]for l < r && nums[l] <= base {l++}nums[r] = nums[l]}nums[l] = basereturn l
}