java ac solution using stack


  • 0
    public class RandomizedCollection {
        List<Integer> list;
        Map<Integer, Stack<Integer>> map;
        java.util.Random rand;
    
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            list = new ArrayList<>();
            map = new HashMap<>();
            rand = new java.util.Random();
        }
    
        /** 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)) {
                Stack<Integer> temp = map.get(val);
                temp.push(list.size());
                list.add(val);
                return false;
            } else {
                Stack<Integer> temp = new Stack<>();
                temp.push(list.size());
                list.add(val);
                map.put(val, temp);
                return true;
            }
        }
    
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            if (!map.containsKey(val)) return false;
            Stack<Integer> temp = map.get(val);
            int i = temp.pop();
            if (temp.size() == 0) {
                map.remove(val);
            }
            if (i != list.size() - 1) {
                int n = list.get(list.size() - 1);
                list.set(i, n);
                Stack<Integer> q = map.get(n);
                q.pop();
                q.push(i);
            }
            list.remove(list.size() - 1);
    
            return true;
        }
    
        /** Get a random element from the collection. */
        public int getRandom() {
            return list.get(rand.nextInt(list.size()));
        }
    }
    

Log in to reply
 

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