Java, HashMap, Arraylist, Arraylist, Sort. [Easy to understand]


  • 0
    S
    public class RandomizedCollection {
        Map<Integer, ArrayList<Integer>> elem_map;
        ArrayList<Integer> arr;
    
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            elem_map = new HashMap<>();
            arr = new ArrayList<>();
        }
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            boolean flag = false;
            ArrayList<Integer> temp = elem_map.get(val);
            arr.add(val);
            if(temp == null){ // If the temp is null [First time element], we need to insert a new arraylist.
                temp = new ArrayList<>();
                flag = true;
            }
            temp.add(arr.size() - 1);
            elem_map.put(val, temp);
            return flag;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            if( elem_map.containsKey(val) == true ){
                ArrayList<Integer> temp = elem_map.get(val);
                int index = temp.get(temp.size() - 1);
                if( temp.size() == 1 ){
                    elem_map.remove(val);
                }
                else{
                    temp.remove(temp.size() - 1);
                    elem_map.put(val, temp);
                }
                int swap_elem = arr.get(arr.size() - 1);
                if( val != swap_elem ){
                    ArrayList<Integer> swap_temp = elem_map.get(swap_elem);
                    swap_temp.set( swap_temp.size() - 1, index );
                    Collections.sort(swap_temp); //To have the largest index to the right.
                    elem_map.put(swap_elem, swap_temp);
                    Collections.swap(arr, index, arr.size() - 1);
                }
                arr.remove(arr.size() - 1);
                return true;
            }
            return false;
        }
        
        /** Get a random element from the collection. */
        public int getRandom() {
            if( arr.size() > 0 ){
                Random rand = new Random();
                int n = rand.nextInt(arr.size());
                return arr.get(n);
            }
            return -1;
        }
    }
    

Log in to reply
 

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