Java solution using one LinkedList and one HashMap


  • 0
    J

    The idea is

    Adding and getting random are trivial. The point of this question is to remove ele in the list/map and keep elements in a sequential order. Therefore, this solution is to swap the to-be-deleted element with the last elements, and remove the last element.

    My code is as follow:

    public class RandomizedSet {
    HashMap<Integer, Integer> map;
    List<Integer> list;
    Random random;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new LinkedList<>();
        map = new HashMap<>();
        random = new Random();
    }
    
    /** 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;
        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 temp = list.get(list.size()-1);
        list.set(map.get(val), temp);
        map.put(temp,map.get(val));
    
        list.remove(list.size()-1);
        map.remove(val);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int n = random.nextInt(list.size());
        return list.get(n);
    }
    

    }


Log in to reply
 

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