LeetCode，数组中的第K个最大元素
力扣题目：
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
- 来源：力扣（LeetCode）
- 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
解题
1. 冒泡排序
「冒泡排序」：依次比较两个相邻的元素，如果是逆序（从小到大）（a[j]>a[j+1]），则将其交换，最终达到有序化; 冒泡排序，每一轮排序都会将最大值排列出来（第一轮将第一大值置于倒数第一位置，第二轮将第二大值置于倒数第二位置...），所以，根据题目求第 k 个最大的元素，我们只需轮询K次即可。 最后返回 [数组长度-K] 下标的值即为所求。
func findKthLargest(nums []int, k int) int {
l := len(nums)
for i :=0; i < k; i++ {
for j := 0; j < l-1-i; j++ {
if nums[j] > nums[j+1] {
nums[j],nums[j+1] = nums[j+1],nums[j]
}
}
}
return nums[l-k]
}
2. 基于快速排序的选择方法
我们可以用快速排序来解决这个问题，先对原数组排序，再返回倒数第 k 个位置，这样平均时间复杂度是 O(nlogn)，我们可以改进快速排序算法来解决这个问题：在分解的过程当中，我们会对子数组进行划分，如果划分得到的 q 正好就是我们需要的下标，就直接返回 a[q]；否则，如果 q 比目标下标小，就递归右子区间，否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。这就是「快速选择」算法。
我们知道快速排序的性能和「划分」出的子数组的长度密切相关。直观地理解如果每次规模为 n 的问题我们都划分成 1 和 n−1，每次递归的时候又向 n−1 的集合中递归，这种情况是最坏的，时间代价是 O(n ^ 2)。我们可以引入随机化来加速这个过程，它的时间代价的期望是 O(n)。
func findKthLargest(nums []int, k int) int {
rand.Seed(time.Now().UnixNano())
return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
}
func quickSelect(a []int, l, r, index int) int {
q := randomPartition(a, l, r)
if q == index {
return a[q]
} else if q < index {
return quickSelect(a, q + 1, r, index)
}
return quickSelect(a, l, q - 1, index)
}
func randomPartition(a []int, l, r int) int {
i := rand.Int() % (r - l + 1) + l
a[i], a[r] = a[r], a[i]
return partition(a, l, r)
}
func partition(a []int, l, r int) int {
x := a[r]
i := l - 1
for j := l; j < r; j++ {
if a[j] <= x {
i++
a[i], a[j] = a[j], a[i]
}
}
a[i+1], a[r] = a[r], a[i+1]
return i + 1
}
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-08-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
