Create a data structure in which insert and delete operations run time costs = O(1).
You should not insert duplicate items. You should just return false if asked to insert a dup item.
You should be able to delete an item from the list given the number to be deleted.
We can use dictionaries and list data structures together to come up with a new type of data structure where the cost of insertion and deletion is just O(1).
public class RandomizedSet {
Dictionary <int,int> ht = new Dictionary<int,int>();
List<int> nums = new List<int>();
public RandomizedSet() {
}
public bool Insert(int val) {
if(ht.ContainsKey(val))
return false;
else {
nums.Add(val);
ht[val] = nums.IndexOf(val);
return true;
}
}
public bool Remove(int val) {
if(!ht.ContainsKey(val))
return false;
else {
nums.Remove(val);
ht.Remove(val);
return true;
}
}
public int GetRandom() {
Random r = new Random();
return nums[r.Next(0,nums.Count-1)];
}
public void Display() {
foreach(int i in nums)
Console.WriteLine(i);
}
}