leetcode

commit 892ece7ba6ed097f987cc1c7863f832d6f96d419
parent b73ec999fe29108f8edd0f74d4864262487e808d
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 15 Dec 2023 20:44:09 +0000

1 Random Problem

Diffstat:
A
Problems/0380.cpp
 | 
27
+++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 28 insertions(+), 0 deletions(-)
diff --git a/Problems/0380.cpp b/Problems/0380.cpp
@@ -0,0 +1,27 @@
+class RandomizedSet {
+  public:
+    RandomizedSet() {}
+
+    bool insert(int val) {
+        if (um.count(val)) return false;
+        nums.emplace_back(val);
+        um[val] = nums.size() - 1;
+        return true;
+    }
+
+    bool remove(int val) {
+        if (!um.count(val)) return false;
+        int last = nums.back();
+        um[last] = um[val];
+        nums[um[val]] = last;
+        nums.pop_back();
+        um.erase(val);
+        return true;
+    }
+
+    int getRandom() { return nums[rand() % nums.size()]; }
+
+  private:
+    vector<int> nums;
+    unordered_map<int, int> um;
+};
diff --git a/README.md b/README.md
@@ -282,6 +282,7 @@ for solving problems.
 |  0376  |   Medium   | [Wiggle Subsequence](Problems/0376.cpp)                                                            |
 |  0377  |   Medium   | [Combination Sum IV](Problems/0377.cpp)                                                            |
 |  0378  |   Medium   | [Kth Smallest Element in a Sorted Matrix](Problems/0378.cpp)                                       |
+|  0380  |   Medium   | [Insert Delete GetRandom O(1)](Problems/0380.cpp)                                                  |
 |  0382  |   Medium   | [Linked List Random Node](Problems/0382.cpp)                                                       |
 |  0383  |    Easy    | [Ransom Note](Problems/0383.cpp)                                                                   |
 |  0384  |   Medium   | [Shuffle an Array](Problems/0384.cpp)                                                              |