Java Solution beats 97%. Totally based on the previous question


  • 1

    It is almost the same as the previous question, the only difference is now we use a Map<Integer,Set> to store the indexes of the numbers in the array list. We can take advantage of the O(1) add and delete of Set, but we can't realize a get in O(1). So this is the trick of the solution. I just use the previous solution -- RandomizedSet again to make sure all operations are O(1). ---> Map<Integer, RandomizedSet> the key represents the element, value represents all indexes of the key.

    /**/
    class RandomizedSet {

    	private List<Integer> list;
    	private Map<Integer, Integer> position;
    	private static Random random = new Random();
    	
    	/* initialzie */
    	public RandomizedSet() {
    		list = new ArrayList<Integer>();
    		position = new HashMap<Integer, Integer>();
    	}
    	
    	/* Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    	public boolean insert(int val) {
    		if (position.containsKey(val))
    			return false;
    		list.add(val);
    		position.put(val, list.size() - 1);
    		return true;
    	}
    	
    	/* Removes a value from the set. Returns true if the set contained the specified element. */
    	public boolean remove(int val) {
    		if (!position.containsKey(val))
    			return false;
    		int p = position.get(val);
    		int lastVal = list.get(list.size() - 1);
    		list.set(p, lastVal);
    		list.remove(list.size() - 1);
    		position.put(lastVal, p);
    		position.remove(val);
    		return true;
    	}
    	
    	/* Get a random element from the set. */
    	public int getRandom() {
    		return list.get(random.nextInt(list.size()));
    	}
    	
    	public int size() {
    		return list.size();
    	}
    	
    }
    

    public class RandomizedCollection {

    private static Random random = new Random();
    private List<Integer> list;
    private Map<Integer, RandomizedSet> positions;
    
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        list = new ArrayList<Integer>();
    	positions = new HashMap<Integer, RandomizedSet>();
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        if (positions.containsKey(val)) {
    		list.add(val);
    		RandomizedSet pVal = positions.get(val);
    		pVal.insert(list.size() - 1);
            return false;
    	}
    	else {
    		RandomizedSet pVal = new RandomizedSet();
    		list.add(val);
    		pVal.insert(list.size() - 1);
            positions.put(val, pVal);
    		return true;
    	}
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (!positions.containsKey(val))
    		return false;
    	if (val == list.get(list.size() - 1)) {
    		RandomizedSet s = positions.get(val);
    		s.remove(list.size() - 1);
    		if (s.size() == 0)
                positions.remove(val);
    		list.remove(list.size() - 1);
    		return true;
    	}
    		
    	RandomizedSet pVal = positions.get(val);
        int pDel = pVal.getRandom();
    	int lastVal = list.get(list.size() - 1);
        RandomizedSet pLast = positions.get(lastVal);
    	pLast.remove(list.size() - 1);
        pLast.insert(pDel);			
    	pVal.remove(pDel);
        if (pVal.size() == 0)
    		positions.remove(val);
    	list.set(pDel, list.get(list.size() - 1));
    	list.remove(list.size() - 1);
    	return true;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
    

    }


Log in to reply
 

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