Java HsahMap and Queue solution accepted


  • 0
    P

    Explanation:
    numToInd: map, use queue to store the indexes
    indToNum: map, store ind to numbers
    deletedInd: queue, use to store deleted indexes. This is to help the get random function. If there are a lot of indexes deleted, the get random function can be very inefficient. If we can reuse the deleted indexes, then the get random function can be slightly better. But this does make the code a slightly complicated.

    public class RandomizedCollection {

    private Map<Integer,Queue<Integer>> numToInd = new HashMap<>();
    private Map<Integer,Integer> indToNum = new HashMap<>();
    private Queue<Integer> deletedInd = new LinkedList<>();
    private int nextInd;
    private Random random = new Random();
    
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        // get the possible index
        int ind = 0;
        if (deletedInd.size() != 0) ind = deletedInd.poll();
        else {
            ind = nextInd;
            nextInd ++;
        }
        indToNum.put(ind,val); // put ind to num in map
        // add index in the index queue if num exist
        if (numToInd.containsKey(val)) {
            numToInd.get(val).add(ind);
            return false;
        }
        // create new queue if the number does not exist
        Queue<Integer> temp = new LinkedList<>();
        temp.add(ind);
        numToInd.put(val,temp);
        return true;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (!numToInd.containsKey(val)) return false;
        Queue<Integer> inds = numToInd.get(val);
        if (inds.size() == 1) numToInd.remove(val);
        deletedInd.add(inds.peek());
        indToNum.remove(inds.poll());
        return true;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        int ind = random.nextInt(nextInd);
        while (!indToNum.containsKey(ind)) ind = random.nextInt(nextInd);
        return indToNum.get(ind);
    }
    

    }


  • 0

    @pigabc Not sure your getRamdon() is avg O(1)..
    if the nextInt is 100,000 and there is only one int left in the queue, then this getRamdon() only has 1/100,000 chance to get the only int and stuck in the while loop for a long time.


Log in to reply
 

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