Java Solution with PriorityQueue in HashMap


  • 0

    I used PriorityQueue in HashMap to store information!

    class RandomizedCollection {
    
        /** Initialize your data structure here. */
        Random rnd;
        HashMap<Integer, PriorityQueue<Integer>> map;
        List<Integer> list;
        public RandomizedCollection() {
            list = new LinkedList<>();
            rnd = new Random();
            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.get(val).isEmpty()) {
                map.get(val).add(list.size());
                list.add(val);
                return false;
            }else{
                map.put(val, new PriorityQueue<>(1, (a, b)-> Integer.compare(b, a)));
                map.get(val).add(list.size());
                list.add(val);
                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) || map.get(val).isEmpty()) return false;
            int position = map.get(val).peek();
            int lastVal = list.get(list.size() - 1);
            //update
            list.set(position, lastVal);
            map.get(lastVal).poll();
            map.get(lastVal).offer(position);
            
            list.remove(list.size() - 1);
            map.get(val).poll();
            return true;
        }
        
        /** Get a random element from the collection. */
        public int getRandom() {
            return list.get(rnd.nextInt(list.size()));
        }
    }
    
    

Log in to reply
 

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