本文向大家介绍稍许算法的实现:关于如何去除数组中的重复元素,并比较了三种算法之间的效率.全部代码在Xcode的Playground中实现,直观明了,适合Swift学习入门童鞋观赏.

有个前提

如题,很多童鞋立即给出解决方法,无外乎是利用Swift内置的集合(Set)或字典(Dict)的一个特性:过滤重复元素.

但由于集合和字典中元素的顺序是无法保证的,所以这建立在一个前提基础之上:结果数组元素顺序和原数组可以不同!

但本文的算法要求:在剔除重复元素之后,元素顺序和原数组必须相同,这正是数组核心特点:有序性的一种体现.

第一种实现

如果想要简单,就必须要多些限制.

如果数组元素能满足Hashable协议,我们利用内置集合也未尝不可:

extension Array where Element:Hashable{ /// 返回剔除重复元素后的数组,其元素顺序不变 public var noRepetitionUseSet:[Element]{ var set = Set<Element>(self) var resultAry = [Element]()  for item in self{ if set.contains(item){ 	//只会保留第一个重复元素!!! resultAry.append(item) set.remove(item) } } return resultAry }}

如上,我们首先用集合过滤所有重复的元素,然后遍历数组,只保留第一个重复的元素.这样原有数组的顺序即得以保持不变.

数组操作是麻烦之源

如果不能保证数组元素满足Hashable协议,至少它们要满足Equatable协议.

这里略微复杂的地方在于,动态删除数组的元素需要考虑到它们删除的顺序.

删除后的黑洞立即会被后续所填满,仿佛根本不存在一样. — 鲁迅

还有一个稍微棘手的问题在于:如何计算多个中间数组(它们只是原始数组的部分拷贝)元素在原始数组中对应的索引位置.

所以,这里不如让我们另辟蹊径,利用Swift的另一个特性: Optional!!!

有种类型叫:可有可无!

如果可以解决下面问题,就会使算法简单很多:

不用直接删除重复元素简化定位元素的位置

这时Optional前来拯救我们了.

其核心思想是:不删除重复元素而是将其设置为nil!!!

extension Array where Element:Equatable{ public var noRepetition:[Element]{ var copy:[Element?] = self //下面只有非nil值才有比较的必要. for (i,x) in copy.enumerated(){ if x == nil {continue} for (j,y) in copy[(i+1)...].enumerated(){ if y == nil {continue} if x! == y! { //将原数组中对应的重复元素设置为nil copy[j+i+1] = nil } } } //剔除非空值,保持元素顺序 return copy.compactMap {$0} }}

如上,算法比较复杂,理解起来略微费劲!

永无止境

这个世界永远有更好的解决方法,就看你能不能发现了.

其实在不使用集合和字典的前提下,我们还可以这么写:

public var noRepetition2:[Element]{ var result = [Element]() for item in self{ if !result.contains(item) { result.append(item) } } return result}

我们只需要将每一个非重复的元素,放到一个新数组中,就完美的绕开了上面所有这些麻烦的东东…

问题来了:谁更快?快多少?

那么上面3种方法到底谁更快呢???

因为是在Playground中运行,所以很快能写一个性能计算器来得到答案:

struct Timing{ var start:Date!  mutating func timingStart(){ start = Date() }  func timingStop()->Double{ return Date().timeIntervalSince(start) }  mutating func timing(count:Int,working:()->Void){ var totalTiming:Double = 0.0 for _ in 0..<count{ timingStart() working() totalTiming += timingStop() } print("\(count)次平均执行时间 : \(totalTiming/Double(count))") }}

因为系统的复杂性,我们不可能只用一两次执行来统计准确的运行时间.

测试代码如下:

let a = [1,1,1,2,3,4,1,3,4,5,6,2,1,1,1,1,17,7,7,8,9,2,1,0,1]var t = Timing()t.timing(count: 1000){ _ = a.noRepetitionUseSet}print(a.noRepetitionUseSet)t.timing(count: 1000){ _ = a.noRepetition}print(a.noRepetition)t.timing(count: 1000){ _ = a.noRepetition2}print(a.noRepetition2)

结果如下:

1000次平均执行时间 : 0.002724636197090149

[1, 2, 3, 4, 5, 6, 8, 17, 7, 9, 0]

1000次平均执行时间 : 0.004712764143943787

[1, 2, 3, 4, 5, 6, 8, 17, 7, 9, 0]

1000次平均执行时间 : 0.002008106589317322

[1, 2, 3, 4, 5, 6, 8, 17, 7, 9, 0]

首先可以看到三者返回剔除重复元素后的结果是完全一样的(这是必须的),另外它们的速度是第二种比第一种慢大约2ms左右,而最后一种比第一种还快一点点.我想日常的使用还是可以接受的.

(更正:只是对于[1,1,1,2,3,4,1,3,4,5,6,2,1,1,1,1,17,7,7,8,9,2,1,0,1]这个数组来说,第二种比第一种慢2ms,但随着数组元素个数的增加,后者会比前者慢更多!)

结尾

最后总结一下:

第一种算法利用内置集合类,对数组元素类型有限制,但速度快,逻辑简单.第二种算法依赖更少,但速度稍慢,逻辑略复杂.第三种算法速度最快,依赖少,逻辑最简单,可以作为首选.

虽然第一种方法利用了内部Swift库的优化,但创建集合的时间抵消了优化的时间,所以最后一种方法胜出!!!

上面我们实现了3种剔除重复元素的算法,并且比较了它们的优劣.

大家可以自由选择,如果你有更好的算法,欢迎讨论

这就是所有的内容了.

(PS:最后还有一种很简单的实现:

public var noRepetition3:[Element]{ var curIdx = -1 return self.filter { curIdx += 1 return self.index(of: $0) == curIdx }}

至于原理和速度大家可以遐想一下)

早睡早起,感谢观赏