LeetCode，數組中的第 K 個最大元素
力扣題目：
給定整數數組 nums 和整數 k，請返回數組中第 k 個最大的元素。
請注意，你需要找的是數組排序後的第 k 個最大的元素，而不是第 k 個不同的元素。
-
來源：力扣（LeetCode）
-
鏈接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
解題
- 冒泡排序
「冒泡排序」：依次比較兩個相鄰的元素，如果是逆序（從小到大）（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
}NEW////ARRIVAL
微信公衆號
gophpython
我的微信
wucs_dd
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/VWDqbTaCIWgGYpK0vQ922g