Best Solution: HashSet & ArrayList (JAVA), concise and simple


  • -2

    most people's solution use hashmap instead of hashset to know the index of removed number, but in my opinion, we do not need to know that!

    We can use ls.remove(Integer.valueOf(val)) to directly remove from list!
    So, I believe it will be simpler than other's

    But the only problem is: my O(1) solution is not fast! So, if someone knows the reason why it is slow, plz let me know, thx.

    update: I was helped to found the reason: my solution is O(n) by using the remove method.

    public class RandomizedSet {
        //improved by other's
        //use hashset and arraylist inorder to directly find the random int in O(1)
        Set<Integer> s;
        List<Integer> ls;
        Random rd;
    
        /** Initialize your data structure here. */
        public RandomizedSet() {
            s = new HashSet<>();
            rd = new Random();
            ls = 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(s.contains(val)) return false;
            else{
                s.add(val);
                ls.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(s.contains(val)){
                s.remove(val);
                ls.remove(Integer.valueOf(val));
               return true; 
            } 
            else return false;
        }
    
        /** Get a random element from the set. */
        public int getRandom() {
            //find the int
            return ls.get(rd.nextInt(s.size()));//list can directly find the number with idx==0 to idx == s.size()-1
        }
    }
    
    /**
     * Your RandomizedSet object will be instantiated and called as such:
     * RandomizedSet obj = new RandomizedSet();
     * boolean param_1 = obj.insert(val);
     * boolean param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */

  • 0
    Z

    @Jim39 ArrayList.remove is O(1)?


  • 0

    @ZesinWong ArrayList.remove(int) is O(1), ArrayList.remove(Objective) is O(n), I think mine is O(n)


  • 0
    A

    your delete is O(n) because it has to shift every number to the right of the index over one. To make it constant time you have to swap the element at that index with the last and then delete it.


  • 0

    @alan28 Thank you for your detailed explaination


  • 0
    C

    This question actually tests you how to solve the problem that ArrayList.remove() takes O(n).
    So the answer is that remove(m) where m is the index of the last element, takes O(1).


Log in to reply
 

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