本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Kth Largest Element
第k大元素问题(k-th Largest Element Problem)
你有一个整数数组a。 编写一个算法，在数组中找到第k大的元素。
例如，第1个最大元素是数组中出现的最大值。 如果数组具有n个元素，则第n最大元素是最小值。 中位数是第n/2最大元素。
朴素的解决方案
以下是半朴素的解决方案。 它的时间复杂度是 O(nlogn)，因为它首先对数组进行排序，因此也使用额外的 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() 函数有两个参数：由整数组成的数组a，已经整数k。 它返回第k大元素。
让我们看一个例子并运行算法来看看它是如何工作的。 给定k = 4和数组：
[ 7, 92, 23, 9, -1, 0, 11, 6 ]
最初没有找到第k大元素的直接方法，但在对数组进行排序之后，它非常简单。 这是排完序的数组：
[ -1, 0, 6, 7, 9, 11, 23, 92 ]
现在，我们所要做的就是获取索引a.count - k的值：
a[a.count - k] = a[8 - 4] = a[4] = 9
当然，如果你正在寻找第k个最小的元素，你会使用a [k-1]。
更快的解决方案
有一种聪明的算法结合了二分搜索和快速排序的思想来达到O(n)解决方案。
回想一下，二分搜索会一次又一次地将数组分成两半，以便快速缩小您要搜索的值。 这也是我们在这里所做的。
快速排序还会拆分数组。它使用分区将所有较小的值移动到数组的左侧，将所有较大的值移动到右侧。在围绕某个基准进行分区之后，该基准值将已经处于其最终的排序位置。 我们可以在这里利用它。
以下是它的工作原理：我们选择一个随机基准，围绕该基准对数组进行分区，然后像二分搜索一样运行，只在左侧或右侧分区中继续。这一过程重复进行，直到我们找到一个恰好位于第k位置的基准。
让我们再看看初始的例子。 我们正在寻找这个数组中的第4大元素：
[ 7, 92, 23, 9, -1, 0, 11, 6 ]
如果我们寻找第k个最小项，那么算法会更容易理解，所以让我们采用k = 4并寻找第4个最小元素。
请注意，我们不必先对数组进行排序。 我们随机选择其中一个元素作为基准，假设是11，并围绕它分割数组。 我们最终会得到这样的结论：
[ 7, 9, -1, 0, 6, 11, 92, 23 ]
<------ smaller larger -->
如您所见，所有小于11的值都在左侧; 所有更大的值都在右边。基准值11现在处于最终排完序的位置。基准的索引是5，因此第4个最小元素肯定位于左侧分区中的某个位置。从现在开始我们可以忽略数组的其余部分：
[ 7, 9, -1, 0, 6, x, x, x ]
再次让我们选择一个随机的枢轴，让我们说6，然后围绕它划分数组。 我们最终会得到这样的结论：
[ -1, 0, 6, 9, 7, x, x, x ]
基准值6在索引2处结束，所以显然第4个最小的项必须在右侧分区中。 我们可以忽略左侧分区：
[ x, x, x, 9, 7, x, x, x ]
我们再次随机选择一个基准值，假设是9，并对数组进行分区：
[ x, x, x, 7, 9, x, x, x ]
基准值9的索引是4，这正是我们正在寻找的 k。 我们完成了！ 注意这只需要几个步骤，我们不必先对数组进行排序。
以下函数实现了这些想法：
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)
}
为了保持可读性，功能分为三个内部函数：
-
randomPivot()选择一个随机数并将其放在当前分区的末尾（这是Lomuto分区方案的要求，有关详细信息，请参阅快速排序上的讨论）。 -
randomizedPartition()是Lomuto的快速排序分区方案。 完成后，随机选择的基准位于数组中的最终排序位置。它返回基准值的数组索引。 -
randomizedSelect()做了所有困难的工作。 它首先调用分区函数，然后决定下一步做什么。 如果基准的索引等于我们正在寻找的k元素，我们就完成了。 如果k小于基准索引，它必须回到左分区中，我们将在那里递归再次尝试。 当第k数在右分区中时，同样如此。
很酷，对吧？ 通常，快速排序是一种 O(nlogn) 算法，但由于我们只对数组中较小的部分进行分区，因此randomizedSelect()的运行时间为 O(n)。
注意： 此函数计算数组中第k最小项，其中k从0开始。如果你想要第k最大项，请用
a.count - k。
作者：Daniel Speiser，Matthijs Hollemans
翻译：Andy Ron
校对：Andy Ron
网友评论