Created
August 17, 2016 05:28
-
-
Save jianminchen/9561828feda21bac20bc9ba4da0d13c8 to your computer and use it in GitHub Desktop.
Leetcode 380 - insert, delete, getRandom() O(1) - study code - from blog: http://www.guoting.org/leetcode/leetcode-380-insert-delete-getrandom-o1/
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
public class RandomizedSet { | |
private List<Integer> list; | |
private Map<Integer,Integer> map; | |
java.util.Random rand = new java.util.Random(); | |
/** Initialize your data structure here. */ | |
public RandomizedSet() { | |
list=new ArrayList<>(); | |
map=new HashMap<>(); | |
} | |
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ | |
public boolean insert(int val) { | |
if(map.containsKey(val)) return false; | |
map.put(val,list.size()); | |
list.add(val); | |
return true; | |
} | |
/** Removes a value from the set. Returns true if the set contained the specified element. */ | |
public boolean remove(int val) { | |
if(!map.containsKey(val)) return false; | |
int index=map.get(val); | |
if(index!=list.size()-1){ | |
int last=list.get(list.size()-1); | |
list.set(index,last); | |
map.put(last,index); | |
} | |
map.remove(val); | |
list.remove(list.size()-1); | |
return true; | |
} | |
/** Get a random element from the set. */ | |
public int getRandom() { | |
return list.get(rand.nextInt(list.size())); | |
} | |
} | |
/** | |
* Your RandomizedSet object will be instantiated and called as such: | |
* RandomizedSet obj = new RandomizedSet(); | |
* boolean param_1 = obj.insert(val); | |
* boolean param_2 = obj.remove(val); | |
* int param_3 = obj.getRandom(); | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment