1+ package medium ;
2+
3+ import java .util .HashMap ;
4+ import java .util .HashSet ;
5+ import java .util .Iterator ;
6+ import java .util .Map ;
7+ import java .util .Random ;
8+ import java .util .Set ;
9+
10+ /**This solution get AC'ed. Although it's not really doing random*/
11+ public class RandomizedSet {
12+
13+ Set <Integer >set ;
14+
15+ /** Initialize your data structure here. */
16+ public RandomizedSet () {
17+ set =new HashSet ();
18+ }
19+
20+ /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
21+ public boolean insert (int val ) {
22+ if (set .contains (val ))return false ;
23+ else {
24+ set .add (val );
25+ return true ;
26+ }
27+ }
28+
29+ /** Deletes a value from the set. Returns true if the set contained the specified element. */
30+ public boolean delete (int val ) {
31+ return set .remove (val );
32+ }
33+
34+ /** Get a random element from the set. */
35+ public int getRandom () {
36+ Iterator <Integer >it =set .iterator ();
37+ if (!it .hasNext ())return -1 ;
38+ int res =0 ;
39+ while (it .hasNext ()){
40+ res =it .next ();
41+ break ;
42+ }
43+ return res ;
44+ }
45+
46+ public static void main (String ...args ){
47+ RandomizedSet_2nd_solution test =new RandomizedSet_2nd_solution ();
48+ System .out .println (test .insert (1 ));
49+ System .out .println (test .delete (2 ));
50+ System .out .println (test .insert (2 ));
51+ System .out .println (test .getRandom ());
52+ System .out .println (test .delete (1 ));
53+ System .out .println (test .insert (2 ));
54+ System .out .println (test .getRandom ());
55+ }
56+ }
57+
58+ /**
59+ * Your RandomizedSet object will be instantiated and called as such:
60+ * RandomizedSet obj = new RandomizedSet();
61+ * boolean param_1 = obj.insert(val);
62+ * boolean param_2 = obj.delete(val);
63+ * int param_3 = obj.getRandom();
64+ */
65+
66+ /**TODO: submit this solution on OJ later, it's throwing cannot find symbol remove() method on line 16,
67+ * this is an OJ bug that people reported on Discuss, submit it later, see if it can get AC'ed.*/
68+ class RandomizedSet_2nd_solution {
69+
70+ Map <Integer ,Integer >forwardMap ;//key is auto increment index, value if the inserted val
71+ Map <Integer ,Integer >reverseMap ;//the other way around
72+ int index ;
73+ Random random ;
74+
75+ /** Initialize your data structure here. */
76+ public RandomizedSet_2nd_solution () {
77+ forwardMap =new HashMap ();
78+ reverseMap =new HashMap ();
79+ index =0 ;
80+ random =new Random ();
81+ }
82+
83+ /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
84+ public boolean insert (int val ) {
85+ if (forwardMap .containsValue (val ))return false ;
86+ else {
87+ forwardMap .put (index ,val );
88+ reverseMap .put (val ,index ++);
89+ return true ;
90+ }
91+ }
92+
93+ /** Deletes a value from the set. Returns true if the set contained the specified element. */
94+ public boolean delete (int val ) {
95+ if (forwardMap .containsValue (val )){
96+ int key =reverseMap .get (val );
97+ reverseMap .remove (val );
98+ forwardMap .remove (key );
99+ return true ;
100+ }else {
101+ return false ;
102+ }
103+ }
104+
105+ /** Get a random element from the set. */
106+ public int getRandom () {
107+ int max =forwardMap .size ();
108+ int randomNum =random .nextInt (max ) ==0 ?1 :random .nextInt (max );
109+ return forwardMap .get (randomNum );
110+ }
111+
112+ }