要求用O(1)的時(shí)間復(fù)雜度實(shí)現(xiàn)插入、刪除和隨機(jī)輸出一個(gè)值，python的list可以實(shí)現(xiàn)插入、刪除末尾元素和指定下標(biāo)輸出對(duì)應(yīng)值的O(1)復(fù)雜度，但是在插入和刪除時(shí)需要先判斷該元素是否已經(jīng)存在，這個(gè)操作只有用python的字典才可O(1)實(shí)現(xiàn)，于是開一個(gè)dict用于記錄每個(gè)插入的元素的下標(biāo)，再用list記錄當(dāng)前存在的每個(gè)元素
插入：
用dict判斷該元素是否已經(jīng)存在，如果不存在，則list append這個(gè)元素，dict記錄這個(gè)元素的下標(biāo)（即當(dāng)前有的元素總數(shù)）
刪除：
因?yàn)閘ist只有pop末尾元素才能O(1)，所以先用dict定位到需要?jiǎng)h除的元素的下標(biāo)，然后與list末尾元素交換（注意交換之后dict中保存的list原末尾元素的下標(biāo)也需要更新），以及現(xiàn)有的元素總數(shù)要減1
隨機(jī)輸出list中的一個(gè)值：
python有現(xiàn)成函數(shù)：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()
本來(lái)還想嘗試用C寫，但是需要手工實(shí)現(xiàn)Hash，懶得寫了>_<