第27章：O(n²)排序的进阶
挑战1：元素分组
给定一个可等价元素的集合，把给定值的所有实例带到集合的右边。
挑战2：寻找重复的元素
给定一个可等价（和哈希）元素的集合，返回集合中第一个重复的元素。
挑战3：反转一个集合
用swapAt()手工反转一个元素集合。不要依赖反向或反转方法。
解决方案
挑战1的解决方案
这个问题的诀窍是控制两个引用来管理互换操作。第一个引用将负责寻找下一个需要向右移动的元素，而第二个引用则管理目标交换位置。
这里棘手的部分是要理解你需要什么样的能力。由于你需要改变底层存储，这个函数只适用于MutableCollection类型。
为了有效地完成这个算法，你需要向后的索引遍历，这就是为什么你还要对BidirectionalCollection协议进行约束。
最后，你还需要元素是Equatable的，以针对适当的值。
这个解决方案的时间复杂度是O(n)。
挑战2的解决方案
找到第一个重复的元素是比较简单的。你用一个Set来记录你到目前为止遇到的元素。
这个解决方案可以推广到Sequence，因为它只依赖于元素的迭代。每个元素也必须是Hashable，这样你就可以把它存储在一个集合中。
这个解决方案的时间复杂度是O(n)。
挑战3的解决方案
颠倒一个集合也是比较简单的。再次使用双参考方法，从集合的起点和终点开始互换元素，一直到中间。
一旦你到了中间，你就完成了交换，并且集合被反转。
这个解决方案需要来自MutableCollection的能力，因为你需要对集合进行变异以进行逆转。
你还需要对BidirectionalCollection进行约束，以利用后向索引遍历。
这个解决方案的时间复杂度是O(n)。
| 上一章 | 目录 | 下一章 |
|---|