Can we use HashSet instead of HashMap?


  • 0
    T

    Below code is accepted, can we use HashSet instead of HashMap? Why the run time is slower for HashSet?

    public class RandomizedSet {

    /** Initialize your data structure here. */
    HashSet<Integer> set;
    List<Integer> list;
    
    
    public RandomizedSet() {
        set = new HashSet<>();
        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(set.contains(val))
            return false;
        else {
            set.add(val);
            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(set.contains(val)) {
            set.remove(val);
            list.remove(new Integer(val));
            return true;
        } else
            return false;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        Random random = new Random();
        int index = random.nextInt(list.size());
        return list.get(index);
    }
    

    }


  • 0
    E

    Same as you. I really hope HashSet can solve the problem, but I found it can't actually. Because in the remove method, you use list.remove(new Integer(val)); and the remove method for arraylist is basically scan through the list and delete the element with value val, this is O(n) time complexity.


Log in to reply
 

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