Java AC with short explanation


  • 0
    M

    Basic idea is to maintain a map and list. The map allows lookup in O(1) time. We'll always swap the item that is being removed to the last position of the list before deleting it for O(1) deletion. Get random can be done by generating a random index and returning that item from the list.

    import java.util.Random;
    
    public class RandomizedSet {
        private Map<Integer,Integer> map; // maps integer to the index where this item is stored
        private List<Integer> list;
        /** Initialize your data structure here. */
        public RandomizedSet() {
            map = new HashMap<>();
            list = new ArrayList<>();
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if(map.containsKey(val)) return false; // already mapped
            
            map.put(val, list.size()); 
            list.add(val);
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if(!map.containsKey(val)) return false;
            
            int index = map.get(val); // our val is stored at this index
            if(index==list.size()-1){ // our item is the last item 
                map.remove(val);
                list.remove(list.size()-1);
                return true;
            }
            
            int last = list.get(list.size()-1); // this is the last value in our list
            
            map.remove(val); // remove our val from mapping
            map.put(last,index); // map the last item to our current index
            
            list.set(index,last); // set the current item to equal the last item
            list.remove(list.size()-1); // remove the last item
            
            return true;
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            Random rand = new Random();
            int index = rand.nextInt(list.size());
            return list.get(index);
        }
    }
    '''
    '''
    

Log in to reply
 

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