Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit3410ab0

Browse files
authored
Merge pull requestneetcode-gh#2112 from Maunish-dave/0380-insert-delete-getrandom-o1.cpp
Create 0380-insert-delete-getrandom-o1.cpp
2 parentse170ea3 +6575e24 commit3410ab0

File tree

1 file changed

+57
-0
lines changed

1 file changed

+57
-0
lines changed
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
classRandomizedSet {
2+
public:
3+
4+
unordered_map<int,int> indices;
5+
vector<int> values;
6+
RandomizedSet() {
7+
}
8+
9+
boolinsert(int val) {
10+
11+
if(indices.find(val)==indices.end()){
12+
values.push_back(val);
13+
// store the index of that value
14+
indices[val] = values.size() -1;
15+
returntrue;
16+
}
17+
returnfalse;
18+
}
19+
20+
boolremove(int val) {
21+
22+
if(indices.find(val)==indices.end()){
23+
returnfalse;
24+
}
25+
26+
// find index of the value
27+
int idx = indices[val];
28+
// get the last value in the vector
29+
// and change its index to curr val's index
30+
indices[values[values.size()-1]] = idx;
31+
32+
// replace curr vals index with last
33+
// last value
34+
values[idx] = values[values.size()-1];
35+
36+
// so now the curr val is removed from the
37+
// vector replaced by last value and so
38+
// we could just remove last value
39+
values.pop_back();
40+
41+
// also erase it from the hash map
42+
indices.erase(val);
43+
returntrue;
44+
}
45+
46+
intgetRandom() {
47+
return values[rand()%values.size()];
48+
}
49+
};
50+
51+
/**
52+
* Your RandomizedSet object will be instantiated and called as such:
53+
* RandomizedSet* obj = new RandomizedSet();
54+
* bool param_1 = obj->insert(val);
55+
* bool param_2 = obj->remove(val);
56+
* int param_3 = obj->getRandom();
57+
*/

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp