27.O(n²)排序挑战

挑战1：元素分组

给定一个有Equatable个元素的集合，将所有给定值的实例带到集合的右边。

挑战2：找到一个重复的元素

给出一个Equatable(和Hashable)元素的集合，返回集合中第一个重复的元素。

挑战3：反转一个集合

用swapAt()手工反转一个元素集合。不要依赖reverse或reversed方法。

解决方案

挑战1的解决方案

这个问题的诀窍是控制两个引用来管理互换操作。第一个引用将负责寻找下一个需要向右移动的元素，而第二个引用则负责管理目标交换位置。

extension MutableCollection
  where Self: BidirectionalCollection, Element: Equatable {

  mutating func rightAlign(value: Element) {
    var left = startIndex
    var right = index(before: endIndex)

    while left < right {
      while self[right] == value {
        formIndex(before: &right)
      }
      while self[left] != value {
        formIndex(after: &left)
      }

      guard left < right else {
        return
      }
      swapAt(left, right)
    }
  }
}

这里棘手的部分是要了解你需要什么样的能力。由于你需要改变底层存储，这个函数只适用于MutableCollection类型。

为了有效地完成这个算法，你需要向后的索引遍历，这就是为什么你还要对BidirectionalCollection协议进行约束。

最后，你还需要元素是Equatable，以针对适当的值。

这个解决方案的时间复杂度是O(n)。

挑战2的解决方案

找到第一个重复的元素是比较简单的。你用一个Set来记录到目前为止你所遇到的元素。

extension Sequence where Element: Hashable {

  var firstDuplicate: Element? {
    var found: Set<Element> = []
    for value in self {
      if found.contains(value) {
        return value
      } else {
        found.insert(value)
      }
    }
    return nil
  }
}

这个解决方案被推广到Sequence，因为它只依赖于元素的迭代。每个元素也必须是Hashable，这样你就可以把它存储在一个集合中。

这个解决方案的时间复杂度是O(n)。

挑战3的解决方案

颠倒一个集合也是比较简单的。再一次使用双参考方法，从集合的起点和终点开始交换元素，一直交换到中间。

一旦到了中间，你就完成了交换，集合就反转了。

extension MutableCollection
  where Self: BidirectionalCollection {

  mutating func reverse() {
    var left = startIndex
    var right = index(before: endIndex)

    while left < right {
      swapAt(left, right)
      formIndex(after: &left)
      formIndex(before: &right)
    }
  }
}

这个解决方案需要来自MutableCollection的能力，因为你需要对集合进行变异，以实现反向。

你还需要约束BidirectionalCollection以利用后向索引遍历。

这个解决方案的时间复杂度是O(n)。