edit 380

fishercoder1534 · fishercoder1534 · commit f10b4d27e5b5 · 2017-08-05T09:59:43.000-07:00
diff --git a/README.md b/README.md
@@ -231,6 +231,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |383|[Ransom Note](https://leetcode.com/problems/ransom-note/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_383.java)| O(n)|O(n) | Medium|
 |382|[Linked List Random Node](https://leetcode.com/problems/linked-list-random-node/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_382.java)| O(1)|O(n) | Medium| Reservoir Sampling
 |381|[Insert Delete GetRandom O(1) - Duplicates allowed](https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_381.java)| | | Hard| 
+|380|[Insert Delete GetRandom O(1)](https://leetcode.com/problems/insert-delete-getrandom-o1/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_380.java)| O(n) | O(1)| Medium| Design, HashMap
 |379|[Design Phone Directory](https://leetcode.com/problems/design-phone-directory/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_379.java)| O(1)|O(n) | Medium| 
 |377|[Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_377.java)| O(?)|O(?) | Medium|
 |376|[Wiggle Subsequence](https://leetcode.com/problems/wiggle-subsequence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_376.java)| O(n)|O(1) | Medium| DP, Greedy
diff --git a/src/main/java/com/fishercoder/solutions/RandomizedSet.java b/src/main/java/com/fishercoder/solutions/RandomizedSet.java
diff --git a/src/main/java/com/fishercoder/solutions/_380.java b/src/main/java/com/fishercoder/solutions/_380.java
@@ -0,0 +1,106 @@
+package com.fishercoder.solutions;
+
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Random;
+
+/**
+ * 380. Insert Delete GetRandom O(1)
+ * Design a data structure that supports all following operations in average O(1) time.
+ * <p>
+ * insert(val): Inserts an item val to the set if not already present.
+ * remove(val): Removes an item val from the set if present.
+ * getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
+ * Example:
+ * <p>
+ * // Init an empty set.
+ * RandomizedSet randomSet = new RandomizedSet();
+ * <p>
+ * // Inserts 1 to the set. Returns true as 1 was inserted successfully.
+ * randomSet.insert(1);
+ * <p>
+ * // Returns false as 2 does not exist in the set.
+ * randomSet.remove(2);
+ * <p>
+ * // Inserts 2 to the set, returns true. Set now contains [1,2].
+ * randomSet.insert(2);
+ * <p>
+ * // getRandom should return either 1 or 2 randomly.
+ * randomSet.getRandom();
+ * <p>
+ * // Removes 1 from the set, returns true. Set now contains [2].
+ * randomSet.remove(1);
+ * <p>
+ * // 2 was already in the set, so return false.
+ * randomSet.insert(2);
+ * <p>
+ * // Since 2 is the only number in the set, getRandom always return 2.
+ * randomSet.getRandom();
+ */
+
+public class _380 {
+    /**
+     * Your _380 object will be instantiated and called as such:
+     * _380 obj = new _380();
+     * boolean param_1 = obj.insert(val);
+     * boolean param_2 = obj.delete(val);
+     * int param_3 = obj.getRandom();
+     */
+
+    public static class RandomizedSet {
+
+        Map<Integer, Integer> forwardMap;//key is auto increment index, value if the inserted val
+        Map<Integer, Integer> reverseMap;//the other way around
+        int index;
+        Random random;
+
+        /**
+         * Initialize your data structure here.
+         */
+        public RandomizedSet() {
+            forwardMap = new HashMap();
+            reverseMap = new HashMap();
+            index = 0;
+            random = new Random();
+        }
+
+        /**
+         * Inserts a value to the set. Returns true if the set did not already contain the specified element.
+         */
+        public boolean insert(int val) {
+            if (forwardMap.containsValue(val)) return false;
+            else {
+                forwardMap.put(index, val);
+                reverseMap.put(val, index++);
+                return true;
+            }
+        }
+
+        /**
+         * Deletes a value from the set. Returns true if the set contained the specified element.
+         */
+        public boolean remove(int val) {
+            if (forwardMap.containsValue(val)) {
+                int key = reverseMap.get(val);
+                reverseMap.remove(val);
+                forwardMap.remove(key);
+                return true;
+            } else {
+                return false;
+            }
+        }
+
+        /**
+         * Get a random element from the set.
+         */
+        public int getRandom() {
+            int max = forwardMap.size();
+            if (max == 1) return forwardMap.get(index - 1);
+            int randomNum = random.nextInt(max);
+            while (!forwardMap.containsKey(randomNum)) {
+                randomNum = random.nextInt(max);
+            }
+            return forwardMap.get(randomNum);
+        }
+    }
+}
