Java 133ms


  • 0
    P
    public class RandomizedSet {
        Map<Integer, Integer> map;
        Map<Integer, Integer> mapR;
        int total_number;
        /** Initialize your data structure here. */
        public RandomizedSet() {
            map = new HashMap<Integer, Integer>();
            mapR = new HashMap<Integer, Integer>();
            total_number = 0;
        }
    
         /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if(map.containsKey(val))
                return false;
            else {
                 total_number ++;
                 map.put(val, total_number);
                 mapR.put(total_number, val);
                 return true;
            }
        }
    
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if(map.containsKey(val)) {
                 int index = map.get(val);
                 mapR.remove(index);
                 map.remove(val);
                 int change;
                 if(index == total_number)
            	 change = total_number - 1;
                 else
            	 change = total_number;
                 if(change != 0) {
                     int v = mapR.get(change);
                     map.put(v, index);
                     mapR.put(index, v);
                }
                total_number --;
                return true;
            }
            else {
                return false;
            }
        }
    
        /** Get a random element from the set. */
        public int getRandom() {
            int k = (int)(Math.random() * total_number);
            int r = k % total_number + 1;
            return mapR.get(r);
        }
    }

  • 0
    Z

    @pygmalion same idea


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.