Java ArrayList and two maps solution


  • 1

    I haven't seen this one yet (maybe I overlooked?). I admit, the previous problem completely puzzled me, but once I knew the solution for it, this one was a breeze.

    The idea came to me at once: if I need a linear distribution, I need to keep all duplicates in a single array. But how do I map values to indexes if values may contain duplicates? Keeping only the last one obviously won't do the trick because deletion will be impossible. So what do I do? And the next thought was: well, if I need values to be different to map them to indexes, let's make them different!

    So I introduced a simple structure to store values. Each value is accompanied by the sequence number, which is unique among all duplicated values. This allows me to map freely and basically to solve the problem in exactly the same way as the previous one. The only place where I really needed the auxiliary data structure is the map, but I also kept value instances in the array to make code cleaner. Note that it probably doesn't cost me any additional memory since I have to keep those instances in the map anyway, and a reference to a structure is probably consuming even less memory than a boxed integer (screw Java generics!).

        private final List<Value> values = new ArrayList<>();
        private final Map<Value, Integer> indexes = new HashMap<>();
        private final Map<Integer, Integer> counts = new HashMap<>();
        private final Random random = new Random();
        
        public boolean insert(int val) {
            return appendNewValue(val).wasAddedFirst();
        }
    
        private Value appendNewValue(int val) {
            Value newValue = new Value(val, counts.getOrDefault(val, 0));
            values.add(newValue);
            indexes.put(newValue, values.size() - 1);
            counts.put(val, newValue.number + 1);
            return newValue;
        }
        
        public boolean remove(int val) {
            int count = counts.getOrDefault(val, 0);
            if (count == 0)
                return false;
            int index = indexes.get(new Value(val, count - 1));
            swapWithLastValue(index);
            removeLastValue();
            return true;
        }
    
        private void swapWithLastValue(int index) {
            int lastIndex = values.size() - 1;
            Value temp = values.get(index);
            Value last = values.get(lastIndex);
            values.set(index, last);
            values.set(lastIndex, temp);
            indexes.put(last, index);
            indexes.put(temp, lastIndex);
        }
    
        private void removeLastValue() {
            int lastIndex = values.size() - 1;
            Value value = values.get(lastIndex);
            values.remove(lastIndex);
            indexes.remove(value);
            if (value.wasAddedFirst())
                counts.remove(value.value);
            else
                counts.put(value.value, value.number);
        }
        
        public int getRandom() {
            return values.get(random.nextInt(values.size())).value;
        }
        
        private static class Value {
            private final int value;
            private final int number;
    
            public Value(int value, int number) {
                this.value = value;
                this.number = number;
            }
    
            @Override
            public int hashCode() {
                int hash = 3;
                hash = 13 * hash + this.value;
                hash = 13 * hash + this.number;
                return hash;
            }
    
            @Override
            public boolean equals(Object obj) {
                if (this == obj)
                    return true;
                if (obj == null || getClass() != obj.getClass())
                    return false;
                final Value other = (Value) obj;
                return this.value == other.value
                        && this.number == other.number;
            }
    
            boolean wasAddedFirst() {
                return number == 0;
            }
        }
    

Log in to reply
 

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