【译】Swift算法俱乐部-有序集
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/Ordered Set
有序集（Ordered Set）
我们来看看苹果如何实现有序集。
Here is the example about how it works
以下是有关其工作原理的示例：
let s = AppleOrderedSet<Int>()
s.add(1)
s.add(2)
s.add(-1)
s.add(0)
s.insert(4, at: 3)
print(s.all()) // [1, 2, -1, 4, 0]
s.set(-1, at: 0) // 已经有-1在index: 2，因此这个操作不做任何事情
print(s.all()) // [1, 2, -1, 4, 0]
s.remove(-1)
print(s.all()) // [1, 2, 4, 0]
print(s.object(at: 1)) // 2
print(s.object(at: 2)) // 4
显着的区别是数组没有排序。 插入时，数组中的元素是相同的。 将数组映像为不重复且具有 O(logn) 或 O(1) 搜索时间。
这里的想法是使用数据结构来提供 O(1) 或 O(logn) 时间复杂度，因此很容易考虑哈希表。
var indexOfKey: [T: Int]
var objects: [T]
indexOfKey is used to track the index of the element. objects is array holding elements.
indexOfKey 用于跟踪元素的索引。 objects是数组保持元素。
我们将在这里详细介绍一些关键功能。
添加
更新indexOfKey并在objects的末尾插入元素
// O(1)
public func add(_ object: T) {
guard indexOfKey[object] == nil else {
return
}
objects.append(object)
indexOfKey[object] = objects.count - 1
}
插入
在数组的随机位置插入将花费 O(n) 时间。
// O(n)
public func insert(_ object: T, at index: Int) {
assert(index < objects.count, "Index should be smaller than object count")
assert(index >= 0, "Index should be bigger than 0")
guard indexOfKey[object] == nil else {
return
}
objects.insert(object, at: index)
indexOfKey[object] = index
for i in index+1..<objects.count {
indexOfKey[objects[i]] = i
}
}
设置
如果object已存在于OrderedSet中，则什么也不做。 否则，我们需要更新indexOfkey和objects。
// O(1)
public func set(_ object: T, at index: Int) {
assert(index < objects.count, "Index should be smaller than object count")
assert(index >= 0, "Index should be bigger than 0")
guard indexOfKey[object] == nil else {
return
}
indexOfKey.removeValue(forKey: objects[index])
indexOfKey[object] = index
objects[index] = object
}
删除
删除数组中的元素将花费 O(n)。 同时，我们需要在删除元素后更新所有元素的索引。
// O(n)
public func remove(_ object: T) {
guard let index = indexOfKey[object] else {
return
}
indexOfKey.removeValue(forKey: object)
objects.remove(at: index)
for i in index..<objects.count {
indexOfKey[objects[i]] = i
}
}
