125ms Java Solution, kind of cheating


  • 0
    M

    My idea is to maintain an ArrayList pool to store values inserted, an HashMap index to store the mapping from values to their indices and a Queue holes to store all the "holes" after remove value in pool. To get a random element in the set, simply keep generating random index until the corresponding value in pool is not a hole (nonempty). To lower the retries, the RandomSet keeps the number of holes (size of holes) less than half of the size of the pool. Therefore the probability of 1 retry is 50%, of 2 retries is 25%, of 3 retries is 12.5 and so on. The probability of more than 3 reties is small. Therefore we could consider the complexity of getRandom is constant in average.

    To achieve this, every time remove an element from the RandomSet, check whether the number of holes is larger than half of the pool. If it is, it constructs a new ArrayList newPool, reconstructs the mapping from values to indices and empties the holes. It takes O(n) time to reconstruct them but like appending an ArrayList, the possibility is low. The average time complexity is O(1) for each remove.

    When inserting a new element, exam if there are available holes. If it is, poll a hole from the holes and put the new element to that hole in pool. If not, just append it to pool with a new mapping in index.

    public class RandomizedSet {
        private int count;
        private ArrayList<Integer> pool;
        private Map<Integer, Integer> index;
        private Queue<Integer> holes;
        private Random random;
    
        /** Initialize your data structure here. */
        public RandomizedSet() {
            this.count = 0;
            this.pool = new ArrayList<Integer>();
            this.index = new HashMap<Integer, Integer>();
            this.holes = new LinkedList<Integer>();
            this.random = new Random();
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if (index.containsKey(val)){
                return false;
            }
            Integer i = this.holes.poll();
            if (i != null) { /* There are still holes in the holes pool */
                this.pool.set(i, val);
                this.index.put(val, i);
            } else { /* There are no holes left in the holes pool. Extends the pool in this case */
                this.pool.add(val);
                this.index.put(val, this.pool.size() - 1);
            }
            this.count++;
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if (!index.containsKey(val)) {
                return false;
            }
            int i = this.index.get(val);
            this.holes.offer(i);
            this.pool.set(i, null);
            this.index.remove(val);
            this.count--;
            if (this.count * 2 < this.pool.size()) {
                ArrayList<Integer> newPool = new ArrayList<Integer>();
                int curr = 0;
                this.index.clear();
                for (Integer p: this.pool) {
                    if (p != null) {
                        newPool.add(p);
                        this.index.put(p, curr++);
                    }
                }
                this.pool = newPool;
                this.holes = new LinkedList<Integer>();
            }
            return true;
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            Integer ret = null;
            while (ret == null) {
                int randomIndex = this.random.nextInt(this.pool.size());
                ret = this.pool.get(randomIndex);
            }
            return ret;
        }
    }
    

Log in to reply
 

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