给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
「冒泡排序」:依次比较两个相邻的元素,如果是逆序(从小到大)(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]
}
我们可以用快速排序来解决这个问题,先对原数组排序,再返回倒数第 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
}