Fork me on GitHub

【译】Swift算法俱乐部-有序集

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.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
以下是有关其工作原理的示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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) 时间复杂度,因此很容易考虑哈希表。

1
2
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的末尾插入元素

1
2
3
4
5
6
7
8
9
// O(1)
public func add(_ object: T) {
guard indexOfKey[object] == nil else {
return
}

objects.append(object)
indexOfKey[object] = objects.count - 1
}

插入

在数组的随机位置插入将花费 O(n) 时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 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中,则什么也不做。 否则,我们需要更新indexOfkeyobjects

1
2
3
4
5
6
7
8
9
10
11
12
13
// 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)。 同时,我们需要在删除元素后更新所有元素的索引。

1
2
3
4
5
6
7
8
9
10
11
12
// 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
}
}

作者:Kai Chen
翻译:Andy Ron
校对:Andy Ron

坚持原创技术分享,您的支持将鼓励我继续创作!
0%