音乐网站开发技术,效果好的魔站建站系统,如何制作5分钟宣传片视频,怎样做网站能百度能搜到数组中的第 K 个最大元素
题目#xff1a;数组中的第 K 个最大元素
给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。
请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1…数组中的第 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, pos1, 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[i1] {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-min1) minpos : partition(nums, min, max, randN)if pos index {return nums[pos]} else if pos index {return quickSort(nums, pos1, 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
}理论上期望时间复杂度为O(n)求证算法导论中文版.pdf · FaithLight/books - Gitee.com定位《算法导论》9.2
