Created
August 16, 2016 20:51
-
-
Save jianminchen/9ebfbe7462c17689344578be31c804c0 to your computer and use it in GitHub Desktop.
Leetcode 380 - Insert Delete GetRandom O(1) - source code reference from Java - http://www.programcreek.com/2014/08/leetcode-insert-delete-getrandom-o1-java/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace Leetcode380_InsertDeleteGetRandomO_1_ | |
{ | |
class RandomizedSet | |
{ | |
/* | |
* August 16, 2016 | |
* | |
* Leetcode 380 | |
* | |
* Design a data structure that supports all following operations in 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. | |
* | |
* Source code from: | |
* http://www.programcreek.com/2014/08/leetcode-insert-delete-getrandom-o1-java/ | |
* | |
* Write a C# version: | |
* | |
* We can use two hashmaps to solve this problem. One uses value as keys and the other uses index as the keys. | |
*/ | |
static void Main(string[] args) | |
{ | |
RandomizedSet randomSet = new RandomizedSet(); | |
randomSet.insert(1); | |
bool result = randomSet.remove(2); // should be false | |
randomSet.insert(2); | |
int res2 = randomSet.getRandom(); // should be 1 or 2 | |
bool res3 = randomSet.remove(1); // return true | |
randomSet.insert(2); // return false | |
int res4 = randomSet.getRandom(); | |
} | |
Dictionary<Int32, Int32> map1; | |
Dictionary<Int32, Int32> map2; | |
Random rand; | |
/** Initialize your data structure here. */ | |
/* | |
* http://stackoverflow.com/questions/4016483/get-time-in-milliseconds-using-c-sharp | |
issue: long -> int | |
* | |
* Figure out later | |
*/ | |
public RandomizedSet() { | |
map1 = new Dictionary<Int32, Int32>(); | |
map2 = new Dictionary<Int32, Int32>(); | |
rand = new Random((int)(DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond)); | |
} | |
/** | |
* | |
* Inserts a value to the set. Returns true if the set does not contain | |
* the specified element. | |
* | |
* map1 - using value as key | |
* value is the size of map2 - count of numbers in the map 2. | |
* map2 - using number as key, where the number is related to map1's count. | |
* key value starts from 0, increment one by one when new value is added. | |
*/ | |
public bool insert(int val) { | |
if(map1.ContainsKey(val)) | |
return false; | |
int[] arr = new int[2]{map1.Count, map2.Count}; | |
map1.Add(val, arr[0]); | |
map2.Add(arr[1], val); | |
return true; | |
} | |
/** | |
* | |
* Removes a value from the set. Returns true if the set contains | |
* the specified element. | |
* | |
* Tricky part - Julia adds the comment | |
* collision may happen - need to remove last one in map2 | |
* map2 last value will be written again, since count of map decrements one. | |
* | |
* In order to avoid collision, when the number is removed from map1, map2, | |
* then, need to set last one in the map2 to replace the slot removing, and also | |
* add a new entry to map1 as well. | |
* | |
* So many tasks for the function: | |
* 1.remove an entry in two maps | |
* map1 - remove the entry - by val | |
* map2 - remove the entry - by index | |
* | |
* 2. map2 last entry should be added into the map2 | |
* with key - index, | |
* also, the entry should be updated in map1 as well. | |
* put the position of removed item. | |
* | |
* Get into details, step by step: | |
* lastPos = map2.Count - 1; | |
* map1 | |
* key value | |
* val index <- to be removed | |
* map2 | |
* key value | |
* index ? <- to be removed | |
* | |
* And then, | |
* map2 <- last entry before removing | |
* key value | |
* lastPos map2[lastPos] <- since lastPos decrements one | |
* | |
* key1 = map2[lastPos] | |
* | |
* fill the removed slot in map1: | |
* map1[key1] = index; | |
* | |
* map2: | |
* 1. remove last entry | |
* map2.Remove(map2.Count); | |
* 2. map2.Add(index, key1) | |
*/ | |
public bool remove(int val) { | |
if (!map1.ContainsKey(val)) | |
return false; | |
int index = map1[val]; | |
int lastPos = map2.Count - 1; // map2 | |
//remove the entry from both maps | |
map1.Remove(val); | |
map2.Remove(index); | |
if(map1.Count == 0){ | |
return true; | |
} | |
//if last is deleted, do nothing | |
if(index == map1.Count){ | |
return true; | |
} | |
//update the last element's index | |
int relocationKey = map2[lastPos]; | |
//map1.Add(relocationKey, index); // Runtime Execution error - existed already | |
map1[relocationKey] = index; // with the debugger help | |
// move last entry of map2 to the empty slot from 0 to lastPos | |
map2.Remove(lastPos); // remove last one | |
map2.Add(index, relocationKey); | |
return true; | |
} | |
/** | |
* | |
* Get a random element from the set. | |
*/ | |
public int getRandom() { | |
if(map1.Count == 0){ | |
return -1; | |
} | |
if(map1.Count == 1){ | |
return map2[0]; | |
} | |
return map2[new Random().Next(map1.Count)]; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
highlights of the practice:
A. Do not notice that map1 should also update the last entry in the map2 accordingly.
B. map1 should not be action - Add, should be an update - line 157 - run time exception error, 158 fix of bug
C. Declare lastPos in the line: 139
D. There are more than one task in the function remove() from line 133 - 165
look for better ideas to write the function
Write map2 - update function