77import java .util .Random ;
88import java .util .Set ;
99
10- /**This solution get AC'ed. Although it's not really doing random 8/4/2016
10+ /**This solution got AC'ed. Although it's not really doing random 8/4/2016, it got rejected ever since because they added test case
11+ * to see if it's really randomized.
1112 * Now, they've updated the test case and also the question description: Each element must have the same probability of being returned.*/
1213public class RandomizedSet {
1314
@@ -46,13 +47,26 @@ public int getRandom() {
4647
4748public static void main (String ...args ){
4849RandomizedSet_2nd_solution test =new RandomizedSet_2nd_solution ();
49- System .out .println (test .insert (1 ));
50- System .out .println (test .delete (2 ));
51- System .out .println (test .insert (2 ));
52- System .out .println (test .getRandom ());
53- System .out .println (test .delete (1 ));
50+
51+ //test 1:
52+ // System.out.println(test.remove(0));
53+ // System.out.println(test.remove(0));
54+ // System.out.println(test.insert(0));
55+ // System.out.println(test.getRandom());
56+ // System.out.println(test.remove(0));
57+ // System.out.println(test.insert(0));
58+
59+ //test 2:
60+ System .out .println (test .insert (0 ));
5461System .out .println (test .insert (2 ));
62+ System .out .println (test .insert (1 ));
63+ System .out .println (test .insert (1 ));
64+ System .out .println (test .insert (1 ));
65+ System .out .println (test .remove (0 ));
66+ System .out .println (test .insert (0 ));
5567System .out .println (test .getRandom ());
68+ System .out .println (test .insert (1 ));
69+ System .out .println (test .remove (2 ));
5670 }
5771}
5872
@@ -64,6 +78,7 @@ public static void main(String...args){
6478 * int param_3 = obj.getRandom();
6579 */
6680
81+ //this is right and got AC'ed.
6782class RandomizedSet_2nd_solution {
6883
6984Map <Integer ,Integer >forwardMap ;//key is auto increment index, value if the inserted val
@@ -104,7 +119,11 @@ public boolean remove(int val) {
104119/** Get a random element from the set. */
105120public int getRandom () {
106121int max =forwardMap .size ();
107- int randomNum =random .nextInt (max ) ==0 ?1 :random .nextInt (max );
122+ if (max ==1 )return forwardMap .get (index -1 );
123+ int randomNum =random .nextInt (max );
124+ while (!forwardMap .containsKey (randomNum )) {
125+ randomNum =random .nextInt (max );
126+ }
108127return forwardMap .get (randomNum );
109128 }
110129