【译】Swift算法俱乐部-查找最大／最小值

本文是对 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/Select Minimum Maximum

目标：查找未排序数组中的最大/最小值。

最大值或最小值

我们有一个通用对象数组，我们迭代所有对象，跟踪遇到的最小/最大元素。

例子

假设我们想在未排序列表[8,3,9,4,6]中找到最大值。

选择第一个数字8，并将其存储作为目前为止的最大元素。

从列表中选择下一个数字3，并将其与当前最大值进行比较。 3小于8所以最大值8不会改变。

从列表中选择下一个数字9，并将其与当前最大值进行比较。 9大于8所以我们存储9作为最大值。

重复此过程，直到处理完列表中的所有元素。

代码

在Swift中的一个简单实现：

func minimum<T: Comparable>(_ array: [T]) -> T? {
  guard var minimum = array.first else {
    return nil
  }

  for element in array.dropFirst() {
    minimum = element < minimum ? element : minimum
  }
  return minimum
}

func maximum<T: Comparable>(_ array: [T]) -> T? {
  guard var maximum = array.first else {
    return nil
  }

  for element in array.dropFirst() {
    maximum = element > maximum ? element : maximum
  }
  return maximum
}

将代码放在 playground 测试：

1
2
3

let array = [ 8, 3, 9, 4, 6 ]
minimum(array)   // This will return 3
maximum(array)   // This will return 9

Swift的标准库

Swift库已经包含一个叫做SequenceType的扩展，它可返回序列中的最小/最大元素。

1
2
3

let array = [ 8, 3, 9, 4, 6 ]
array.minElement()   // This will return 3
array.maxElement()   // This will return 9

let array = [ 8, 3, 9, 4, 6 ]
//swift3
array.min()   // This will return 3
array.max()   // This will return 9

最大值和最小值

要同时查找数组中包含的最大值和最小值，为了最小化比较次数，我们可以成对比较。

例子

假设我们想要在未排序列表[8,3,9,6,4]中找到最小值和最大值。

选择第一个数字8，并将其存储为目前为止的最小和最大值。

因为我们有一个奇数项目，我们从列表中删除8，留下两队[3,9]和[6,4]。

从列表中选择下一对数字，[3,9]。在这两个数字中，3是较小的数字，因此我们将3与当前最小值8进行比较，并将9与当前最大值8进行比较。 3小于8，所以新的最小值是3。 9大于8，所以新的最大值是9。

从列表中选择下一对数字，[6,4]。这里，4是较小的一个，所以我们将4与当前最小3进行比较，并将6与当前最大9进行比较。 4大于3，所以最小值不会改变。 6小于9，因此最大值不会改变。

结果是最小值为3，最大值为9。

代码

在Swift中的一个简单实现：

func minimumMaximum<T: Comparable>(_ array: [T]) -> (minimum: T, maximum: T)? {
  guard var minimum = array.first else {
    return nil
  }
  var maximum = minimum

  // if 'array' has an odd number of items, let 'minimum' or 'maximum' deal with the leftover
  let start = array.count % 2 // 1 if odd, skipping the first element
  for i in stride(from: start, to: array.count, by: 2) {
    let pair = (array[i], array[i+1])

    if pair.0 > pair.1 {
      if pair.0 > maximum {
        maximum = pair.0
      }
      if pair.1 < minimum {
        minimum = pair.1
      }
    } else {
      if pair.1 > maximum {
        maximum = pair.1
      }
      if pair.0 < minimum {
        minimum = pair.0
      }
    }
  }

  return (minimum, maximum)
}

在playground测试：

1
2
3

let result = minimumMaximum(array)!
result.minimum   // This will return 3
result.maximum   // This will return 9

通过成对挑选元素并将其最大值和最小值与当前的最小值和最大值进行比较，我们将每2个元素的比较次数减少到3次。

性能

这些算法以O(n)运行。将数组中的每个对象与当前的最小值/最大值进行比较，所花费的时间与数组长度成比例。

作者：Chris Pilcher
翻译：Andy Ron
校对：Andy Ron