一道有意思的算法题

Posted on | Edited on | In | | Views:

一道有意思的算法题

实现一个数据结构, 要求

  1. key - val 形式
  2. 插入的时间复杂度是 $O(1)$
  3. get()的时间复杂度是 $O(1)$
  4. delete()的时间复杂度是 $O(1)$
  5. getRandomVal()的时间复杂度是 $O(1)$

思路

如果不看第五点的要求, 那么这个数据结构非常简单, 就是一个哈希表. 但是哈希表不能满足第5点的要求. 因为哈希表的getRandomVal()的时间复杂度是$O(n)$. 所以这个问题的关键点在如何改进哈希表.

如果要想getRandomVal()是一个$O(1)$的操作, 那么必须要去维护一个数组, 因为数组的getRandomValue()的操作是满足$O(1)$的复杂度要求的. 可是, 当在数据结构中额外维护一个数组的时候, 那个删除的操作就会变成$O(n)$. 因为你需要从数组当中删除, 还需要从key-val对子中删除.

很多时候, 就会卡在这里, 因为删除数组的操作一定是一个$O(n)$的操作. 可是仔细想想, 一定要删除数组吗? 删除数组真的是必要的操作吗? 举个例子, 比如说我数组里面的数据是 [1, 2, 3, 4] 当我要删除 2 的时候, 我只需要吧 2 和 4 的位置换一下, 然后把数组的”长度” -1 就可以 了. 这样就实现了一个 $O(1)$的 “删除” 操作.

为了配合数组的操作, 我们需要在val里加上一个对应数组的index. 比如说, 我要插入 (1, a) 这个对子, 在哈希表里的数据应该长这样: <1, (a, 0)>

实现

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
class SuperMap(object):
    def __init__(self):
        self.mapping = dict()
        self.array = list()
        self.length = 0
    
    def insert(self, key, val):
        self.array.append(key)
        self.array[self.length], self.array[-1] = self.array[-1], self.array[self.length]
        self.mapping[key] = (val, self.length)
        self.length += 1
        
    def delete(self, key):
        index = self.mapping[key][1]
        self.array[index], self.array[self.length-1] = self.array[self.length-1], self.array[index]
        self.mapping[self.array[index]] = (self.mapping[self.array[index]][0], index)
        self.length -= 1
        del self.mapping[key]

    def getRandomVal(self):
        import random
        rand_index = random.randint(0, self.length-1)
        return self.mapping[self.array[rand_index]]
    
    def getVal(self, key):
        return self.mapping[key]

总结

这类优化时间复杂度的题目, 往往都是一个路子, 那就是空间换时间. 多想想一些操作是不是真的必要.

EOF