Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
要求用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,懒得写了>_<

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理