Java using 3 HashMaps and An ArrayList (131ms)


  • 0
    L

    Use a countMap to count number of times of a value;
    Use locs map to store index of a value+"#"+current count;
    Use index map for the reverse of locs;

    public class RandomizedCollection {
        ArrayList<Integer> nums;
         HashMap<String, Integer> locs;
         HashMap<Integer,String> indexMap;
         HashMap<Integer,Integer> countMap;
         java.util.Random rand = new java.util.Random();
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            nums = new ArrayList<Integer>();
             locs = new HashMap<String, Integer>();
             indexMap = new HashMap<Integer,String>();
             countMap = new HashMap<Integer,Integer>();
        }
       
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            boolean contain = countMap.containsKey(val);
             if ( ! contain ) countMap.put( val, 1);
             else {
                 countMap.put(val, countMap.get(val)+1);
             }
             nums.add(val);
             int count = countMap.get(val);
             locs.put(val+"#"+count,nums.size()-1);
             indexMap.put(nums.size()-1,val+"#"+count);
             return ! contain ;
        }
       
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            boolean contain = countMap.containsKey(val);
             if ( ! contain ) return false;
             int count = countMap.get(val);
             int loc = locs.get(val+"#"+count);
             if (loc < nums.size() - 1 ) {
                int lastone = nums.get( nums.size()-1 );
                String lastoneStr = indexMap.get(nums.size()-1);
                nums.set( loc , lastone );
                locs.put(lastoneStr,loc);
                indexMap.put(loc,lastoneStr);
             }
             nums.remove(nums.size() - 1);
             locs.remove(val+"#"+count);
             if (count==1) {
                 countMap.remove(val);
             }
             else countMap.put(val,--count);
             return true;
        }
       
        /** Get a random element from the collection. */
        public int getRandom() {
            return nums.get( rand.nextInt(nums.size()) );
        }
    }
    
    

Log in to reply
 

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