[LintCode 657] Insert Delete GetRandom O(1)
Description
Design a data structure that supports all following operations in average O(1) time.
insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
设计一个数据结构实现在平均 O(1) 的复杂度下执行以下所有的操作。
insert(val): 如果这个元素不在set中，则插入。
remove(val): 如果这个元素在set中，则从set中移除。
getRandom: 随机从set中返回一个元素。每一个元素返回的可能性必须相同。
https://www.lintcode.com/problem/insert-delete-getrandom-o1/description
Example:
// 初始化空集set
RandomizedSet randomSet = new RandomizedSet();
// 1插入set中。返回正确因为1被成功插入
randomSet.insert(1);
// 返回错误因为2不在set中
randomSet.remove(2);
// 2插入set中，返回正确，set现在有[1,2]。
randomSet.insert(2);
// getRandom 应该随机的返回1或2。
randomSet.getRandom();
// 从set中移除1，返回正确。set现在有[2]。
randomSet.remove(1);
// 2已经在set中，返回错误。
randomSet.insert(2);
// 因为2是set中唯一的数字，所以getRandom总是返回2。
randomSet.getRandom();
Note
- O（1）下进行插入和移除操作需要直接在尾部添加元素，并在需要删除某一元素时知晓其位置信息直接进行操作，而不需要遍历
- HashMap可以用来保存数组中数字的下标及其数值的对应关系
- 对于is in 操作，在Dictionary中可以保证O(1)时间完成，而在Array不可以,会是O(n)
下列描述来自九章算法
使用数组来保存当前集合中的元素，同时用一个hashMap来保存数字与它在数组中下标的对应关系。
插入操作时：
若已存在此元素返回false
不存在时将新的元素插入数组最后一位，同时更新hashMap。
删除操作时：
若不存在此元素返回false
存在时先根据hashMap得到要删除数字的下标，再将数组的最后一个数放到需要删除的数的位置上，删除数组最后一位，同时更新hashMap。
获取随机数操作时：
根据数组的长度来获取一个随机的下标，再根据下标获取元素。
Update Review
Code
Python3 on LintCode
check in vals is better than nums!
import random
class RandomizedSet(object):
def __init__(self):
# do intialization if necessary
self.nums = []
self.vals = {}
"""
@param: val: a value to the set
@return: true if the set did not already contain the specified element or false
"""
def insert(self, val):
# write your code here
if val in self.nums:
return False
self.nums.append(val)
self.vals[val] = len(self.nums) - 1
return True
"""
@param: val: a value from the set
@return: true if the set contained the specified element or false
"""
def remove(self, val):
# write your code here
# check in vals is better than nums!
if val not in self.vals:
return False
index, last = self.vals[val], self.nums[-1]
self.vals[index], self.vals[last] = last, index
self.nums.pop()
del self.vals[val]
return True
"""
@return: Get a random element from the set
"""
def getRandom(self):
# write your code here
return self.nums[random.randint(0, len(self.nums) - 1)]
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param = obj.insert(val)
# param = obj.remove(val)
# param = obj.getRandom()
Ref Code
本参考程序来自九章算法
import random
class RandomizedSet(object):
def __init__(self):
# do initialize if necessary
self.nums, self.pos = [], {}
# @param {int} val Inserts a value to the set
# Returns {bool} true if the set did not already contain the specified element or false
def insert(self, val):
if val in self.pos:
return False
self.nums.append(val)
self.pos[val] = len(self.nums) - 1
return True
# @param {int} val Removes a value from the set
# Return {bool} true if the set contained the specified element or false
def remove(self, val):
# Write your code here
if val not in self.pos:
return False
idx, last = self.pos[val], self.nums[-1]
self.nums[idx], self.pos[last] = last, idx
self.nums.pop()
del self.pos[val]
return True
# return {int} a random number from the set
def getRandom(self):
return self.nums[random.randint(0, len(self.nums) - 1)]
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param = obj.insert(val)
# param = obj.remove(val)
# param = obj.getRandom()
This blog is under a CC BY-NC-SA 3.0 Unported License
本文使用 CC BY-NC-SA 3.0 中国 协议许可
署名-非商业性使用-相同方式共享（BY-NC-SA）：使用者可以对本创作进行共享、演绎，但使用时须进行署名（同时标明是否（对原始作品）作了修改），且不得运用于商业目的，采用本创作的内容必须同样采用本协议进行授权。详情请参考协议细则。
本文链接：https://dataleoz.com/lintcode-insert-delete-getrandom/