Java solution with two HashMaps, 132 ms


  • 0
    P

    It uses two Map, and one queue. So the space is 2N. The queue is used to store the deleted indexes to make the getRandom function faster.

    public class RandomizedSet {

    private int nextInd = 0;
    Queue<Integer> queue = new LinkedList<>(); // to store the deleted indexes
    Map<Integer,Integer> numToInd = new HashMap<>();
    Map<Integer,Integer> indToNum = new HashMap<>();
    Random random = new Random();
    
    /** Initialize your data structure here. */
    public RandomizedSet() {
        
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (numToInd.containsKey(val)) return false;
        int ind = 0;
        if (queue.size() != 0) ind = queue.poll();
        else {
            ind = nextInd;
            nextInd ++;
        }
        numToInd.put(val,ind);
        indToNum.put(ind,val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!numToInd.containsKey(val)) return false;
        int ind = numToInd.get(val);
        numToInd.remove(val);
        indToNum.remove(ind);
        queue.add(ind);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int ind = random.nextInt(nextInd);
        while (!indToNum.containsKey(ind)) ind = random.nextInt(nextInd);
        return indToNum.get(ind);
    }
    

    }


Log in to reply
 

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