本文是對 Swift Algorithm Club 翻譯的一篇文章霜定。
Swift Algorithm Club是 raywenderlich.com網(wǎng)站出品的用Swift實現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)的開源項目塔鳍，目前在GitHub上有18000+??，我初略統(tǒng)計了一下，大概有一百左右個的算法和數(shù)據(jù)結(jié)構(gòu)般此，基本上常見的都包含了盖文，是iOSer學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)不錯的資源砍濒。
??andyRon/swift-algorithm-club-cn是我對Swift Algorithm Club，邊學(xué)習(xí)邊翻譯的項目叫潦。由于能力有限蝇完，如發(fā)現(xiàn)錯誤或翻譯不妥，請指正，歡迎pull request短蜕。也歡迎有興趣氢架、有時間的小伙伴一起參與翻譯和學(xué)習(xí)??。當然也歡迎加??朋魔，??????????岖研。
本文的翻譯原文和代碼可以查看??swift-algorithm-club-cn/Kth Largest Element
第k大元素問題(k-th Largest Element Problem)
你有一個整數(shù)數(shù)組a。 編寫一個算法警检，在數(shù)組中找到第k大的元素孙援。
例如，第1個最大元素是數(shù)組中出現(xiàn)的最大值扇雕。 如果數(shù)組具有n個元素拓售，則第n最大元素是最小值。 中位數(shù)是第n/2最大元素洼裤。
樸素的解決方案
以下是半樸素的解決方案邻辉。 它的時間復(fù)雜度是 O(nlogn)，因為它首先對數(shù)組進行排序腮鞍，因此也使用額外的 O(n) 空間值骇。
func kthLargest(a: [Int], k: Int) -> Int? {
let len = a.count
if k > 0 && k <= len {
let sorted = a.sorted()
return sorted[len - k]
} else {
return nil
}
}
kthLargest() 函數(shù)有兩個參數(shù)：由整數(shù)組成的數(shù)組a，已經(jīng)整數(shù)k移国。 它返回第k大元素吱瘩。
讓我們看一個例子并運行算法來看看它是如何工作的。 給定k = 4和數(shù)組：
[ 7, 92, 23, 9, -1, 0, 11, 6 ]
最初沒有找到第k大元素的直接方法迹缀，但在對數(shù)組進行排序之后使碾，它非常簡單。 這是排完序的數(shù)組：
[ -1, 0, 6, 7, 9, 11, 23, 92 ]
現(xiàn)在祝懂，我們所要做的就是獲取索引a.count - k的值：
a[a.count - k] = a[8 - 4] = a[4] = 9
當然票摇，如果你正在尋找第k個最小的元素，你會使用a [k-1]砚蓬。
更快的解決方案
有一種聰明的算法結(jié)合了二分搜索和快速排序的思想來達到O(n)解決方案矢门。
回想一下，二分搜索會一次又一次地將數(shù)組分成兩半，以便快速縮小您要搜索的值。 這也是我們在這里所做的沾谓。
快速排序還會拆分數(shù)組矢腻。它使用分區(qū)將所有較小的值移動到數(shù)組的左側(cè)，將所有較大的值移動到右側(cè)。在圍繞某個基準進行分區(qū)之后，該基準值將已經(jīng)處于其最終的排序位置。 我們可以在這里利用它叛薯。
以下是它的工作原理：我們選擇一個隨機基準浑吟，圍繞該基準對數(shù)組進行分區(qū)，然后像二分搜索一樣運行案训，只在左側(cè)或右側(cè)分區(qū)中繼續(xù)买置。這一過程重復(fù)進行，直到我們找到一個恰好位于第k位置的基準强霎。
讓我們再看看初始的例子忿项。 我們正在尋找這個數(shù)組中的第4大元素：
[ 7, 92, 23, 9, -1, 0, 11, 6 ]
如果我們尋找第k個最小項，那么算法會更容易理解城舞，所以讓我們采用k = 4并尋找第4個最小元素轩触。
請注意，我們不必先對數(shù)組進行排序家夺。 我們隨機選擇其中一個元素作為基準脱柱，假設(shè)是11，并圍繞它分割數(shù)組拉馋。 我們最終會得到這樣的結(jié)論：
[ 7, 9, -1, 0, 6, 11, 92, 23 ]
<------ smaller larger -->
如您所見榨为，所有小于11的值都在左側(cè); 所有更大的值都在右邊』蛙睿基準值11現(xiàn)在處于最終排完序的位置随闺。基準的索引是5蔓腐，因此第4個最小元素肯定位于左側(cè)分區(qū)中的某個位置矩乐。從現(xiàn)在開始我們可以忽略數(shù)組的其余部分：
[ 7, 9, -1, 0, 6, x, x, x ]
再次讓我們選擇一個隨機的樞軸，讓我們說6回论，然后圍繞它劃分數(shù)組散罕。 我們最終會得到這樣的結(jié)論：
[ -1, 0, 6, 9, 7, x, x, x ]
基準值6在索引2處結(jié)束，所以顯然第4個最小的項必須在右側(cè)分區(qū)中傀蓉。 我們可以忽略左側(cè)分區(qū)：
[ x, x, x, 9, 7, x, x, x ]
我們再次隨機選擇一個基準值欧漱，假設(shè)是9，并對數(shù)組進行分區(qū)：
[ x, x, x, 7, 9, x, x, x ]
基準值9的索引是4葬燎，這正是我們正在尋找的 k误甚。 我們完成了！ 注意這只需要幾個步驟萨蚕，我們不必先對數(shù)組進行排序靶草。
以下函數(shù)實現(xiàn)了這些想法：
public func randomizedSelect<T: Comparable>(_ array: [T], order k: Int) -> T {
var a = array
func randomPivot<T: Comparable>(_ a: inout [T], _ low: Int, _ high: Int) -> T {
let pivotIndex = random(min: low, max: high)
a.swapAt(pivotIndex, high)
return a[high]
}
func randomizedPartition<T: Comparable>(_ a: inout [T], _ low: Int, _ high: Int) -> Int {
let pivot = randomPivot(&a, low, high)
var i = low
for j in low..<high {
if a[j] <= pivot {
a.swapAt(i, j)
i += 1
}
}
a.swapAt(i, high)
return i
}
func randomizedSelect<T: Comparable>(_ a: inout [T], _ low: Int, _ high: Int, _ k: Int) -> T {
if low < high {
let p = randomizedPartition(&a, low, high)
if k == p {
return a[p]
} else if k < p {
return randomizedSelect(&a, low, p - 1, k)
} else {
return randomizedSelect(&a, p + 1, high, k)
}
} else {
return a[low]
}
}
precondition(a.count > 0)
return randomizedSelect(&a, 0, a.count - 1, k)
}
為了保持可讀性蹄胰，功能分為三個內(nèi)部函數(shù)：
randomPivot()選擇一個隨機數(shù)并將其放在當前分區(qū)的末尾（這是Lomuto分區(qū)方案的要求岳遥，有關(guān)詳細信息，請參閱快速排序上的討論）裕寨。randomizedPartition()是Lomuto的快速排序分區(qū)方案浩蓉。 完成后派继，隨機選擇的基準位于數(shù)組中的最終排序位置。它返回基準值的數(shù)組索引捻艳。randomizedSelect()做了所有困難的工作驾窟。 它首先調(diào)用分區(qū)函數(shù)，然后決定下一步做什么认轨。 如果基準的索引等于我們正在尋找的k元素绅络，我們就完成了。 如果k小于基準索引嘁字，它必須回到左分區(qū)中恩急，我們將在那里遞歸再次嘗試。 當?shù)?em>k數(shù)在右分區(qū)中時纪蜒，同樣如此衷恭。
很酷，對吧纯续？ 通常随珠，快速排序是一種 O(nlogn) 算法，但由于我們只對數(shù)組中較小的部分進行分區(qū)猬错，因此randomizedSelect()的運行時間為 O(n)窗看。
注意： 此函數(shù)計算數(shù)組中第k最小項，其中k從0開始兔魂。如果你想要第k最大項烤芦，請用
a.count - k。
作者：Daniel Speiser析校，Matthijs Hollemans
翻譯：Andy Ron
校對：Andy Ron
