|
1 | 1 | classRandomizedSet { |
2 | 2 |
|
3 | | -privateList<Integer>randomizedSet; |
4 | | -privateMap<Integer,Integer>indexMap; |
5 | | -privateintcurrSize; |
6 | | - |
7 | | -publicRandomizedSet() { |
8 | | -this.randomizedSet =newArrayList<>(); |
9 | | -this.indexMap =newHashMap<>(); |
10 | | -this.currSize =0; |
11 | | - } |
| 3 | +privatefinalList<Integer>values; |
| 4 | +privatefinalMap<Integer,Integer>valToIndexMap; |
12 | 5 |
|
13 | | -publicbooleaninsert(intval) { |
14 | | -if (this.indexMap.containsKey(val)) { |
15 | | -returnfalse; |
| 6 | +publicRandomizedSet() { |
| 7 | +this.values =newArrayList<>(); |
| 8 | +this.valToIndexMap =newHashMap<>(); |
16 | 9 | } |
17 | | -this.randomizedSet.add(val); |
18 | | -this.indexMap.put(val,this.currSize++); |
19 | | -returntrue; |
20 | | - } |
21 | 10 |
|
22 | | -publicbooleanremove(intval) { |
23 | | -if (!this.indexMap.containsKey(val)) { |
24 | | -returnfalse; |
| 11 | +publicbooleaninsert(intval) { |
| 12 | +if (valToIndexMap.containsKey(val)) { |
| 13 | +returnfalse; |
| 14 | + } |
| 15 | +values.add(val); |
| 16 | +valToIndexMap.put(val,values.size() -1); |
| 17 | +returntrue; |
25 | 18 | } |
26 | | -intvalIdx =this.indexMap.get(val); |
27 | | -this.indexMap.put(this.randomizedSet.get(this.currSize -1),valIdx); |
28 | | -this.randomizedSet.set(valIdx,this.randomizedSet.get(this.currSize -1)); |
29 | | -this.randomizedSet.remove(this.currSize -1); |
30 | | -this.indexMap.remove(val); |
31 | | -this.currSize--; |
32 | | -returntrue; |
33 | | - } |
34 | 19 |
|
35 | | -publicintgetRandom() { |
36 | | -returnthis.randomizedSet.get(newRandom().nextInt(this.currSize)); |
37 | | - } |
| 20 | +publicbooleanremove(intval) { |
| 21 | +if (!valToIndexMap.containsKey(val)) { |
| 22 | +returnfalse; |
| 23 | + } |
| 24 | +intvalIdx =valToIndexMap.get(val); |
| 25 | +intvalAtLastIdx =values.get(values.size() -1); |
| 26 | +// update index for last element |
| 27 | +values.set(valIdx,valAtLastIdx); |
| 28 | +valToIndexMap.put(valAtLastIdx,valIdx); |
| 29 | +// remove value |
| 30 | +values.remove(values.size() -1); |
| 31 | +valToIndexMap.remove(val); |
| 32 | +returntrue; |
| 33 | + } |
| 34 | + |
| 35 | +publicintgetRandom() { |
| 36 | +intidx =newRandom().nextInt(values.size()); |
| 37 | +returnvalues.get(idx); |
| 38 | + } |
38 | 39 | } |
39 | 40 |
|
40 | 41 | /** |
|