Posted on 2022-11-29 20:17
Uriel 阅读(44)
评论(0) 编辑 收藏 引用 所属分类:
闲来无事重切Leet Code 、
大水题
要求用O(1)的时间复杂度实现插入、删除和随机输出一个值，python的list可以实现插入、删除末尾元素和指定下标输出对应值的O(1)复杂度，但是在插入和删除时需要先判断该元素是否已经存在，这个操作只有用python的字典才可O(1)实现，于是开一个dict用于记录每个插入的元素的下标，再用list记录当前存在的每个元素
插入：
用dict判断该元素是否已经存在，如果不存在，则list append这个元素，dict记录这个元素的下标（即当前有的元素总数）
删除：
因为list只有pop末尾元素才能O(1)，所以先用dict定位到需要删除的元素的下标，然后与list末尾元素交换（注意交换之后dict中保存的list原末尾元素的下标也需要更新），以及现有的元素总数要减1
随机输出list中的一个值：
python有现成函数：random.choice
1 #380
2 #Runtime: 875 ms
3 #Memory Usage: 59.1 MB
4
5 class RandomizedSet(object):
6
7 def __init__(self):
8 self.random_set = []
9 self.id_cnt = 0
10 self.id_set = {}
11
12 def insert(self, val):
13 """
14 :type val: int
15 :rtype: bool
16 """
17 if val in self.id_set:
18 return False
19 self.random_set.append(val)
20 self.id_set[val] = self.id_cnt
21 self.id_cnt += 1
22 return True
23
24 def remove(self, val):
25 """
26 :type val: int
27 :rtype: bool
28 """
29 if val not in self.id_set:
30 return False
31 idx = self.id_set[val]
32 self.random_set[idx] = self.random_set[-1]
33 self.id_set[self.random_set[-1]] = idx
34 self.id_set.pop(val)
35 self.random_set.pop()
36 self.id_cnt -= 1
37 return True
38
39 def getRandom(self):
40 """
41 :rtype: int
42 """
43 return random.choice(self.random_set);
44
45
46 # Your RandomizedSet object will be instantiated and called as such:
47 # obj = RandomizedSet()
48 # param_1 = obj.insert(val)
49 # param_2 = obj.remove(val)
50 # param_3 = obj.getRandom()
本来还想尝试用C写，但是需要手工实现Hash，懒得写了>_<