127ms Java solution with HashMap, ArrayList and Deque


  • 0
    X
        List<Integer> list;
        Map<Integer, Deque<Integer>> map;
        
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            list = new ArrayList<>();
            map = new HashMap<>();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            if (!map.containsKey(val)) {
                map.put(val, new LinkedList<Integer>());
                map.get(val).offerLast(list.size());
                list.add(val);
                return true;
            } else {
                map.get(val).offerLast(list.size());
                list.add(val);
                return false;
            }
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            if (!map.containsKey(val) || map.get(val).isEmpty()) {
                return false;
            } else {
                if (list.get(list.size() - 1) == val) {
                    list.remove(list.size() - 1);
                    map.get(val).pollLast();
                } else {
                    int val_index = map.get(val).pollLast();
                    int lastIndex = list.size() - 1;
                    int lastNum = list.get(lastIndex);
                    list.set(val_index, lastNum);
                    list.remove(lastIndex);
                    map.get(lastNum).pollLast();
                    if (map.get(lastNum).isEmpty() || val_index > map.get(lastNum).peekLast()) {
                        map.get(lastNum).offerLast(val_index);
                    } else {
                       map.get(lastNum).offerFirst(val_index); 
                    }
                }
                return true;
            }
        }
        
        /** Get a random element from the collection. */
        public int getRandom() {
            if (list == null || list.size() == 0) return -1;
            Random rand = new Random();
            int randIndex = rand.nextInt(list.size());
            return list.get(randIndex);
        }
    }

Log in to reply
 

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