Java no HashSet, no LinkedHashSet, based on two-way indexing


  • 0

    For each element we add into the ArrayList nums we also attach its index in the LinkedList in HashMap. That way we can always correctly locate the last element of nums in its corresponding LinkedList and update the LinkedList entry value. Thanks clanad_wawa for this brilliant idea.

        private ArrayList<int[]> nums;
        private HashMap<Integer, LinkedList<Integer>> pos;
        private Random r;
        /** Initialize your data structure here. */
        public RandomizedCollection3() {
            nums = new ArrayList<>();
            pos = new HashMap<>();
            r = 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) {
            boolean contains = pos.containsKey(val);
            LinkedList<Integer> list = pos.getOrDefault(val, new LinkedList<>());
            list.add(nums.size());
            nums.add(new int[]{val, list.size()-1});
            pos.put(val, list);
            return !contains;
        }
    
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            if (!pos.containsKey(val)) return false;
            LinkedList<Integer> list1 = pos.get(val);
            int index = list1.removeLast();
            if (list1.isEmpty()) pos.remove(val);
            if (index != nums.size()-1) {
                int[] lastnum = nums.get(nums.size()-1);
                nums.set(index, lastnum);
                LinkedList<Integer> list2 = pos.get(lastnum[0]);
                list2.set(lastnum[1], index);
            }
            nums.remove(nums.size()-1);
            return true;
        }
    
        /** Get a random element from the collection. */
        public int getRandom() {
            return nums.get(r.nextInt(nums.size()))[0];
        }
    

Log in to reply
 

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