本文是对 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) 空间。

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