元素去重

理解 元素去重 问题

集合去重

实际上,在Swift中完成 元素去重 非常的简单,利用 集合的存储同种类型的不同值 的属性即可。

将同一类型且不重复的值无序地储存在一个集合当中。当元素的顺序不那么重要的时候你就可以使用集合来代替数组,或者你需要确保元素不会重复的时候

1
2
3
4
5
6

var list = [1, 2, 6, 3, 2, 5, 1, 9, 6, 1, 2]

let listSet = Set(list)

print("\(Array(listSet))")

输出:

[3, 5, 2, 6, 9, 1]

但是,虽然这个方法非常的简单,可惜其开销并不小,且对数组元素类型有限制。因此,这个方法可用于简单的元素去重,来快速的获取结果。

当数据量大的时候,比如上亿级别的数据的时候,这个上述方法对于计算机资源的消耗很大,因此这个时候我们就需要从算法级别去处理了。

算法去重

排序 + 下标 完成元素去重

第一步

先对这个数组进行一次排序

第二步

再如图所示,两个箭头表示两个边界,红色为左边界,蓝色为右边界。首先将左右边界为数组的前两个数。

然后比较两个边界的值,如果值相等,则蓝色边界向右移动,移动至第一个与左边界值不同的元素才停止。

随后,左边界移到此时右边界的位置,然后右边界右移一位。

之后就循环上面的步骤,直到左边界到最后一位为止。

准备一个新数组,将每次 左边界的元素都存入这个数组中,移动完成后,新数组就是 去重 后的数组了。

Swift中实现起来非常的简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

var list = [1, 2, 6, 3, 2, 5, 1, 9, 6, 1, 2]

// 排序
let newList = list.sorted()

// 特殊情况检查
if newList.count < 2 {
print("count < 2")

}

// 特殊情况检查
if newList.count == 2 {

if newList.first == newList.last {
print("\(newList.first!)")
}
else {
print("\(newList)")
}
}

// 新数组
var finishList = [Int]()

// 左边界
var lelfItem = 0
// 右边界
var rightItem = 0

// 遍历数组
for (index, item) in newList.enumerated() {

if index == 0 {

lelfItem = item
finishList.append(item)
continue
}

rightItem = item

if(lelfItem != rightItem) {

lelfItem = rightItem
finishList.append(item)
}
}

print("finish: \(finishList)")

时间复杂度: O(nlogn)

优点: 解决了集合中对数组元素类型限制的问题(只要元素能够比较,就可以使用),在复杂度也并没有较大的开销

扩展

下标计数法。(基数排序)

Go 笔记 理解排序算法

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×