java using HashMap<Integer,HashSet<Integer>>() and ArrayList. with explaination.151ms


  • 1

    The same as problem one but contains duplicate. So using the key of HashMap to store number and HashSet as the value to store indexes in the list. Every time when the set is empty, remove the key form HashMap.

    Hope it helps~

    public class RandomizedCollection {
    
        /** Initialize your data structure here. */
        HashMap<Integer,HashSet<Integer>> map;
        List<Integer> list;
        java.util.Random r = new java.util.Random();
        public RandomizedCollection() {
            map = new HashMap<Integer,HashSet<Integer>>();
            list = new ArrayList<Integer>();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            list.add(val);
            if(map.containsKey(val)) {
                HashSet<Integer> set = map.get(val);
                set.add(list.size()-1);
                map.put(val , set);
                return false;
            }else {
                HashSet<Integer> set = new HashSet<Integer>();
                set.add(list.size()-1);
                map.put(val , set);
                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)) {
                HashSet<Integer> set = map.get(val);
                Iterator<Integer> it = set.iterator();
                int index = 0;
                if(it.hasNext()) {
                    index = it.next();
                }else {
                    return false;
                }
                set.remove(index);
                if(set.isEmpty()) {
                    map.remove(val);
                }
                if(index == list.size()-1) {
                    list.remove(list.size()-1);
                    return true;
                }else {
                    int deletenum = list.get(index);
                    int lastnum = list.get(list.size()-1);
                    if(lastnum == deletenum) { //if the last number in the list equals to the number to be delete
                        set.remove(list.size() - 1);
                        set.add(index);
                        list.remove(list.size() - 1);
                    }else {
                        list.set(index , lastnum);
                        HashSet<Integer> lastnumset = map.get(lastnum);
                        lastnumset.remove(list.size() - 1);
                        lastnumset.add(index);
                        list.remove(list.size() - 1);
                    }
                    return true;
                }
            }else {
                return false;
            }
        }
        
        /** Get a random element from the collection. */
        public int getRandom() {
            int index = r.nextInt(list.size());
            return list.get(index);
        }
    }
    
    /**
     * Your RandomizedCollection object will be instantiated and called as such:
     * RandomizedCollection obj = new RandomizedCollection();
     * boolean param_1 = obj.insert(val);
     * boolean param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */

  • 0
    F

    Nice solution. Thanks a lot.

    But you could remove the checking in remove since the size of the set is always >= 1 if map.containsKey(val) equals true. Just keep the line for retrieving index.

    if (it.hasNext()) {
         index = it.next();
    } else {
         return false;
    }
    

  • 0
    W

    You can code like this, much shorter.

    public class RandomizedCollection {
    
        Map<Integer, Set<Integer>> map = new HashMap<>();
    
        List<Integer> list = new ArrayList<>();
    
        Random random = new Random();
    
        Set<Integer> set;
    
        public boolean insert(int val) {
          (set = map.computeIfAbsent(val, k -> new HashSet<>())).add(list.size());
          list.add(val);
          return set.size() == 1;
        }
    
        public boolean remove(int val) {
          if ((set = map.get(val)) == null || set.isEmpty()) return false;
          int idx = set.iterator().next(), lastIdx = list.size() - 1, last = list.get(lastIdx);
          set.remove(idx);
          if (idx != lastIdx) {
            (set = map.get(last)).remove(lastIdx);
            set.add(idx);
            list.set(idx, last);
          }
          list.remove(lastIdx);
          return true;
        }
    
        public int getRandom() {
          return list.get(random.nextInt(list.size()));
        }
      }

Log in to reply
 

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