自定义数据结构 Multiset

发表于 分类于 Disqus：

实现一个名叫 Multiset 的集合数据结构，要具有如下的方法

  1. count(for:) 返回相应数据的存储个数；
  2. add(_:) 添加数据；
  3. 删除数据remove(_:)。

举例：

1
2
3
4
5
6
7
8
m = Multiset()
m.add("cat")
m.add("dog")
m.add("cat")

m.count(for: "cat") -> 2
m.remove("cat")
m.count(for: "cat") -> 1

实现一

我的第一感觉是像一个数组一样的数据结构，所以并没有考虑时间复杂度方面的问题，就直接往下继续了，实现细节如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Multiset<T: Equatable> {
    var ary: [T] = []

    mutating func add(_ element: T) {
        ary.append(element)
    }

    func count(for element: T) -> Int {
        let filterResult = ary.filter { $0 == element }
        return filterResult.count
    }

    mutating func remove(_ element: T) {
        if let idx = ary.firstIndex(of: element) {
            ary.remove(at: idx)
        }
    }
}

这里时间复杂度确实有待优化的地方，下面我们换成字典的形式再来一次。

实现二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Multiset<T: Hashable> {
    var dict: [T: Int] = [:]
    
    mutating func add(_ element: T) {
        dict[element, default: 0] += 1
    }
    
    func count(for element: T) -> Int {
        return dict[element] ?? 0
    }
    
    mutating func remove(_ element: T) {
        guard var count = dict[element] else { return }
        count -= 1
        if count > 0 {
            dict[element] = count
        } else {
            dict.removeValue(forKey: element)
        }
    }
}

这回好多了。

路漫漫其修远兮，吾将上下而求索。

我写的可能有点简略，更详细的叙述请看这里：Multiset