RandomQueue-based Solution in Java, accepted, but very slow


  • 0
    F

    The tricky part is that, I use an ArrayList to keep all the elements, and a HashMap for value-index mappings. Then, every time I remove an element, I find its index by the HashMap, and switch the last element of the ArrayList into it. In this way, we don't have to move all the elements after the removed one, which costs us linear time. Still, we have a uniform probability distribution over the rest elements.
    One more thing, if you are skeptical that the add() and remove() methods of an ArrayList will cost O(n) time due to the possible memory reallocation, that's correct. But that holds true only for a single operation. If these two methods are implemented with some tricks(which we should assume that a standard, high-quality JAVA implementation always does, as these tricks are actually not very hard), then the amortized time complexity for each operation still has a constant time complexity. If you want to know what these tricks are, you can check out the free algorithm courses from Princeton released in Coursera. I think they are introduced in the class on stack and queue.

    import java.security.SecureRandom;
    
    public class RandomizedSet {
    
        private SecureRandom randGenerator;
        private ArrayList<Integer> list;
        private HashMap<Integer, Integer> valIdxMap;
    
        /** Initialize your data structure here. */
        public RandomizedSet() {
            randGenerator = new SecureRandom();
            list = new ArrayList<>();
            valIdxMap = new HashMap<>();
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if(!valIdxMap.containsKey(val)) {
                list.add(val);
                valIdxMap.put(val, list.size()-1);
                
                return true;
            } else {
                return false;
            }
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if(!valIdxMap.containsKey(val)) {
                return false;
            } else {
                int lastVal = list.get(list.size()-1);
                int curValIdx = valIdxMap.get(val);
                
                valIdxMap.put(lastVal, curValIdx);
                valIdxMap.remove(val);
                list.set(curValIdx, lastVal);
                list.remove(list.size()-1);
                
                return true;
            }
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            return list.get(randGenerator.nextInt(list.size()));
        }
    }
    

Log in to reply
 

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