Algorithm
Problem Name: 380. Insert Delete GetRandom O(1)
Implement the RandomizedSet class:
RandomizedSet()Initializes theRandomizedSetobject.bool insert(int val)Inserts an itemvalinto the set if not present. Returnstrueif the item was not present,falseotherwise.bool remove(int val)Removes an itemvalfrom the set if present. Returnstrueif the item was present,falseotherwise.int getRandom()Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in average O(1) time complexity.
Example 1:
Input ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Output [null, true, false, true, 2, true, false, 2] Explanation RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomizedSet.remove(2); // Returns false as 2 does not exist in the set. randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly. randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2]. randomizedSet.insert(2); // 2 was already in the set, so return false. randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
Constraints:
-231 <= val <= 231 - 1- At most
2 *105calls will be made toinsert,remove, andgetRandom. - There will be at least one element in the data structure when
getRandomis called.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
struct item {
int val;
struct item *shadow;
};
#define HASHSZ 100
#define HASHCODE(V) (((unsigned int)V) % HASHSZ)
typedef struct {
struct item *items[HASHSZ];
int num;
} RandomizedSet;
/** Initialize your data structure here. */
RandomizedSet* randomizedSetCreate() {
RandomizedSet *obj = calloc(1, sizeof(RandomizedSet));
return obj;
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool randomizedSetInsert(RandomizedSet* obj, int val) {
struct item *e = obj->items[HASHCODE(val)];
while (e && e->val != val) {
e = e->shadow;
}
if (e) {
return false;
}
e = malloc(sizeof(struct item));
//assert(e);
e->val = val;
e->shadow = obj->items[HASHCODE(val)];
obj->items[HASHCODE(val)] = e;
obj->num ++;
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool randomizedSetRemove(RandomizedSet* obj, int val) {
struct item **pp = &obj->items[HASHCODE(val)];
struct item *e = *pp;
while (e && e->val != val) {
pp = &e->shadow;
e = *pp;
}
if (!e) {
return false;
}
obj->num --;
*pp = e->shadow;
free(e);
return true;
}
/** Get a random element from the set. */
int randomizedSetGetRandom(RandomizedSet* obj) {
int num = 0;
int i = 0, j;
struct item *e = NULL;
if (obj->num == 0) return -1;
j = random() % obj->num;
while (!e && i < HASHSZ && j >= 0) {
e = obj->items[i];
while (e && j > 0) {
e = e->shadow;
j --;
}
i ++;
}
return e->val;
}
void randomizedSetFree(RandomizedSet* obj) {
struct item *e, *n;
int i;
for (i = 0; i < HASHSZ; i ++) {
e = obj->items[i];
while (e) {
n = e->shadow;
free(e);
e = n;
}
}
free(obj);
}
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
#2 Code Example with C++ Programming
Code -
C++ Programming
class RandomizedSet {
public:
RandomizedSet() {}
bool insert(int val) {
if(m.count(val)) return false;
m[val] = v.size();
v.push_back(val);
return true;
}
bool remove(int val) {
if(!m.count(val)) return false;
int num = v.back();
m[num] = m[val];
v[m[val]] = num;
v.pop_back();
m.erase(val);
return true;
}
int getRandom() {
return v[rand() % v.size()];
}
private:
unordered_map < int, int>m;
vector<int>v;
};
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
#3 Code Example with Java Programming
Code -
Java Programming
class RandomizedSet {
private List randomizedSet;
private Map < Integer, Integer> indexMap;
private int currSize;
public RandomizedSet() {
this.randomizedSet = new ArrayList < >();
this.indexMap = new HashMap<>();
this.currSize = 0;
}
public boolean insert(int val) {
if (this.indexMap.containsKey(val)) {
return false;
}
this.randomizedSet.add(val);
this.indexMap.put(val, this.currSize++);
return true;
}
public boolean remove(int val) {
if (!this.indexMap.containsKey(val)) {
return false;
}
int valIdx = this.indexMap.get(val);
this.indexMap.put(this.randomizedSet.get(this.currSize - 1), valIdx);
this.randomizedSet.set(valIdx, this.randomizedSet.get(this.currSize - 1));
this.randomizedSet.remove(this.currSize - 1);
this.indexMap.remove(val);
this.currSize--;
return true;
}
public int getRandom() {
return this.randomizedSet.get(new Random().nextInt(this.currSize));
}
}
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const RandomizedSet = function () {
this.arr = []
this.map = new Map()
}
RandomizedSet.prototype.insert = function (val) {
const {arr, map} = this
if(map.has(val)) return false
const size = arr.length
arr.push(val)
map.set(val, size)
return true
}
RandomizedSet.prototype.remove = function (val) {
const {arr, map} = this
if(!map.has(val)) return false
const idx = map.get(val), last = arr[arr.length - 1]
arr[idx] = last
map.set(last, idx)
arr.pop()
map.delete(val)
return true
}
RandomizedSet.prototype.getRandom = function () {
return this.arr[~~(this.arr.length * Math.random())]
}
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
#5 Code Example with Python Programming
Code -
Python Programming
class RandomizedSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.nums, self.ind = [], {}
def insert(self, val):
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
:type val: int
:rtype: bool
"""
if val not in self.ind:
self.nums += val,
self.ind[val] = len(self.nums) - 1
return True
return False
def remove(self, val):
"""
Removes a value from the set. Returns true if the set contained the specified element.
:type val: int
:rtype: bool
"""
if val in self.ind:
ind, last = self.ind[val], self.nums[-1]
self.nums[ind], self.ind[last] = last, ind
self.nums.pop()
self.ind.pop(val)
return True
return False
def getRandom(self):
"""
Get a random element from the set.
:rtype: int
"""
return random.choice(self.nums)
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _0380_InsertDeleteGetRandom
{
private readonly Random random = new Random();
private readonly IDictionary < int, int> locations;
private readonly IList<int> nums;
/** Initialize your data structure here. */
public _0380_InsertDeleteGetRandom()
{
locations = new Dictionary < int, int>();
nums = new List<int>();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public bool Insert(int val)
{
if (locations.ContainsKey(val)) return false;
locations.Add(val, nums.Count);
nums.Add(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public bool Remove(int val)
{
if (!locations.ContainsKey(val)) return false;
if (locations[val] != nums.Count - 1)
{
nums[locations[val]] = nums[nums.Count - 1];
locations[nums[nums.Count - 1]] = locations[val];
}
locations.Remove(val);
nums.RemoveAt(nums.Count - 1);
return true;
}
/** Get a random element from the set. */
public int GetRandom()
{
var index = random.Next(nums.Count);
return nums[index];
}
}
}
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]