Fork me on GitHub

【译】Swift算法俱乐部-第k大元素问题

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.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) 空间。

1
2
3
4
5
6
7
8
9
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和数组:

1
[ 7, 92, 23, 9, -1, 0, 11, 6 ]

最初没有找到第k大元素的直接方法,但在对数组进行排序之后,它非常简单。 这是排完序的数组:

1
[ -1, 0, 6, 7, 9, 11, 23, 92 ]

现在,我们所要做的就是获取索引a.count - k的值:

1
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。 我们完成了! 注意这只需要几个步骤,我们不必先对数组进行排序。

以下函数实现了这些想法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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

坚持原创技术分享,您的支持将鼓励我继续创作!
0%