Simple idea of using HashMap + ArrayList


  • 0
    public class RandomizedSet {
        
        Map<Integer, Integer> valToIdxMap = new HashMap<>();
        List<Integer> array = new ArrayList<>();
        Random rand = new Random();
    
        public boolean insert(int val) {
            if(valToIdxMap.containsKey(val))
                return false;
            array.add(val);
            valToIdxMap.put(val, array.size()-1);
            return true;
        }
        
        public boolean remove(int val) {
            if(!valToIdxMap.containsKey(val))
                return false;
            int idx = valToIdxMap.get(val);
            if(idx<array.size()-1) {
                array.set(idx, array.get(array.size()-1)); // swap
                valToIdxMap.put(array.get(idx), idx); // update swapped
            }
            array.remove(array.size()-1); // list delete last idx is O(1)
            valToIdxMap.remove(val);
            return true;
        }
        
        public int getRandom() {
            return array.get(rand.nextInt(array.size()));
        }
    }

Log in to reply
 

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