Java use arraylist and hashmap


  • 0
    W
    public class RandomizedCollection { 
        List<Integer> vals;
        Map<Integer, List<Integer>> map;
        Random random;
    
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            vals = new ArrayList<>();
            map = new HashMap<>();
            random = new Random();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            List<Integer> list = map.get(val);
            boolean res = list == null || list.size() == 0 ? true : false;
            if (list == null) { 
                list = new ArrayList<>();
            }
            list.add(vals.size());
            map.put(val, list);
            vals.add(val);
            return res;
        }
        
        /** 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).size() == 0) return false;
            List<Integer> indexes = map.get(val);
            int index = indexes.get(indexes.size() - 1);
            indexes.remove(indexes.size() - 1); //removed the index of last inserted value
            int lastVal = vals.get(vals.size() - 1);
            indexes = map.get(lastVal);
            if (index < vals.size() - 1) { //if the val to be removed is not at
                vals.set(index, lastVal); //the end of the vals list, we should use
                indexes.remove(indexes.size() - 1); // its index to remeber the end of val list
                indexes.add(0, index); //new index should add to the beginning
            }
            vals.remove(vals.size() - 1); //remove the last element of the vals list
            return true;
        }
        
        /** Get a random element from the collection. */
        public int getRandom() {
            return vals.get(random.nextInt(vals.size()));
        }
    }

  • 0
    M

    @w28l30
    Can you please explain the logic. I am not able to understand how are you adding values to List vals.


  • 0
    W

    It is based on Insert Delete GetRandom O(1)

    • The List "vals" holds all the values we inserted, so If an "insert" is called, we add the new value to the "vals" list.
    • However, since duplicate is allowed here, the value of hashmap is also a list. For example, if the vals list is 1, 2, 3, 4, 5 and a duplicate 2 need to be inserted into. First we insert the duplicate 2 into vals list, then the vals list is "1, 2, 3, 4, 5, 2" now. We also need to remember the position of this "2". Then, use the hashmap to get the list of "2", I named it index list her. It only contains "1" before, which is the position of the first 2. Then we add the position of the duplicate 2. So the index list of 2 comes to "1, 5".

Log in to reply
 

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