-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
381.java
131 lines (118 loc) · 4.3 KB
/
381.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
__________________________________________________________________________________________________
sample 52 ms submission
class RandomizedCollection {
private Map<Integer, List<Integer>> valueIndexMap;
private int[] set;
private int size = 0;
/** Initialize your data structure here. */
public RandomizedCollection() {
valueIndexMap = new HashMap<>();
set = new int[2];
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int val) {
boolean isExist = valueIndexMap.containsKey(val);
if (size == set.length) {
resize(2 * set.length);
}
valueIndexMap.putIfAbsent(val, new ArrayList<>());
valueIndexMap.get(val).add(size);
set[size] = val;
size++;
return !isExist;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
boolean isExist = valueIndexMap.containsKey(val);
if (isExist) {
int last = size - 1;
int lastValue = set[last];
List<Integer> list = valueIndexMap.get(val);
int targetIndex = list.remove(list.size() - 1);
if (list.size() == 0) {
valueIndexMap.remove(val);
}
if (targetIndex != last) {
List<Integer> lastList = valueIndexMap.get(lastValue);
lastList.remove(lastList.size() - 1);
lastList.add(0, targetIndex);
set[targetIndex] = lastValue;
}
set[last] = 0;
size--;
if (size > 0 && size == set.length/4) {
resize(set.length/2);
}
}
return isExist;
}
/** Get a random element from the collection. */
public int getRandom() {
Random rand = new Random();
int n = rand.nextInt(size);
return set[n];
}
private void resize(int capacity) {
set = java.util.Arrays.copyOf(set, capacity);
}
}
__________________________________________________________________________________________________
sample 40968 kb submission
class RandomizedCollection {
Random rand;
List<Integer> list;
Map<Integer, Set<Integer>> map;
public RandomizedCollection() {
rand = new Random();
list = new ArrayList();
map = new HashMap();
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int val) {
boolean notContains = true;
if(map.containsKey(val)) {
map.get(val).add(list.size());
list.add(val);
notContains = !notContains;
}else {
map.computeIfAbsent(val, k->new LinkedHashSet());
map.get(val).add(list.size());
list.add(val);
}
return notContains;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if(!map.containsKey(val)) {
return false;
}else {
Set<Integer> indexes = map.get(val);
int index = indexes.iterator().next();
indexes.remove(index);
if(indexes.size() == 0) {
map.remove(val);
}
if(index!=list.size()-1){
int lastVal = list.get(list.size()-1);
Set<Integer> lastValIndexes = map.get(lastVal);
list.set(index, lastVal);
lastValIndexes.remove(list.size()-1);
lastValIndexes.add(index);
}
}
list.remove(list.size()-1);
return true;
}
/** Get a random element from the collection. */
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}
/**
* Your RandomizedCollection object will be instantiated and called as such:
* RandomizedCollection obj = new RandomizedCollection();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
__________________________________________________________________________________________________