refactor 380

fishercoder1534 · fishercoder1534 · commit ebe3226ae011 · 2021-10-21T11:18:16.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_380.java b/src/main/java/com/fishercoder/solutions/_380.java
@@ -13,131 +13,43 @@ public static class Solution1 {
          * credit: https://leetcode.com/problems/insert-delete-getrandom-o1/discuss/85401/Java-solution-using-a-HashMap-and-an-ArrayList-along-with-a-follow-up.-(131-ms)
          */
         public static class RandomizedSet {
-            Map<Integer, Integer> locationMap;
+            Map<Integer, Integer> map;
             List<Integer> list;
             Random random;
 
-            /**
-             * Initialize your data structure here.
-             */
             public RandomizedSet() {
-                locationMap = new HashMap<>();
-                list = new ArrayList<>();
+                map = new HashMap<>();
                 random = new Random();
+                list = new ArrayList<>();
             }
 
-            /**
-             * Inserts a value to the set. Returns true if the set did not already contain the specified element.
-             */
             public boolean insert(int val) {
-                if (locationMap.containsKey(val)) {
+                if (map.containsKey(val)) {
                     return false;
-                } else {
-                    locationMap.put(val, list.size());
-                    list.add(val);
-                    return true;
                 }
+                map.put(val, list.size());
+                list.add(list.size(), val);
+                return true;
             }
 
-            /**
-             * Removes a value from the set. Returns true if the set contained the specified element.
-             */
             public boolean remove(int val) {
-                if (!locationMap.containsKey(val)) {
+                if (!map.containsKey(val)) {
                     return false;
                 } else {
-                    int location = locationMap.get(val);
-                    /**if it's not the last one, then swap the last one with this val*/
-                    if (location < list.size() - 1) {
-                        int lastOne = list.get(list.size() - 1);
-                        list.set(location, lastOne);
-                        locationMap.put(lastOne, location);
-                    }
-                    locationMap.remove(val);
+                    int lastElement = list.get(list.size() - 1);
+                    int index = map.get(val);
+                    list.set(index, lastElement);
+                    map.put(lastElement, index);
                     list.remove(list.size() - 1);
+                    map.remove(val);
                     return true;
                 }
             }
 
-            /**
-             * Get a random element from the set.
-             */
             public int getRandom() {
                 return list.get(random.nextInt(list.size()));
             }
-
         }
     }
 
-    /**
-     * 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 Solution2 {
-        /**This is not ideal and not meeting average O(1) time for all three operations.*/
-        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);
-            }
-        }
-    }
 }
