Posted on 2022-11-29 20:17
Uriel 閱讀(54)
評論(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，懶得寫了>_<