Easy Understanding Java Solution using HashSet


  • 4
    public class RandomizedCollection {
    
        List<Integer> nums;
        Map<Integer, Set<Integer>> map;
        java.util.Random random;
    
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            nums = new ArrayList<>();
            map = new HashMap<>();
            random = new java.util.Random();
        }
    
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            boolean doesContain = map.containsKey(val);
            if(!doesContain) map.put(val, new HashSet<>());
            map.get(val).add(nums.size());
            nums.add(val);
            return !doesContain;
        }
    
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            if(!map.containsKey(val)) return false;
            if(!map.get(val).contains(nums.size()-1)) {
                int currPos = map.get(val).iterator().next();
                int lastVal = nums.get(nums.size() - 1);
                map.get(lastVal).remove(nums.size() - 1);
                map.get(lastVal).add(currPos);
                map.get(val).remove(currPos);
                map.get(val).add(nums.size() - 1);
                nums.set(currPos, lastVal);
            }
            map.get(val).remove(nums.size()-1);
            if(map.get(val).isEmpty()) map.remove(val);
            nums.remove(nums.size()-1);
            return true;
        }
    
        /** Get a random element from the collection. */
        public int getRandom() {
            return nums.get(random.nextInt(nums.size()));
        }
    }
    

  • 1
    W

    Nice answer

    You can code with new Java 8's feature to shorten the code like below

    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()));
        }
    }

  • 0
    L

    nice to see you here xiaohei~


  • 0

    @wit I'll try it next time!


  • 0

  • 0
    M
    This post is deleted!

  • 0
    M

    @xietao0221 Doesn't this instruction "nums.set(currPos, lastVal)" make your remove function run in O(n) ?


  • 0
    L
    This post is deleted!

  • 0
    L
    This post is deleted!

Log in to reply
 

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