Leetcode 705) Design HashSet

08 Nov 2021 in Algorithms

My solution

• the denominator is better to be big prime number -> Then, there would be a lot more different remainder values, which will reduce time to look up the target value.

class MyHashSet {
    private LinkedList[] bucket;
    private int room = 10000;
    //

    public MyHashSet() {
        //prime number can generates multiple different remainder.
        bucket = new LinkedList[room];
        for(int i =0;i<room;i++){
            bucket[i]= new LinkedList<Integer>();
        }
    }

    public void add(int key) {
        //no repeating keys
        if(!contains(key)){
            bucket[hashCode(key)].add(key); 
        }

    }

    public void remove(int key) {
        LinkedList<Integer> l =bucket[hashCode(key)];
        for(int i =0;i<l.size();i++){
            if(l.get(i)==key){
                l.remove(i);
            }
        }
    }

    public boolean contains(int key) {
        LinkedList<Integer> l =bucket[hashCode(key)];
        for(int i =0;i<l.size();i++){
            if(l.get(i)==key){
                return true;
            }
        }
        return false;
    }
    public int hashCode(int key){
        return key%room;
    }

}
/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */

Different solution

class MyHashSet {
    boolean[] set;
    public MyHashSet() {
        set = new boolean[1];
    }

    public void add(int key) {
        if (key > set.length - 1) {
            boolean[] temp = new boolean[key + set.length * 2];
            System.arraycopy(set, 0, temp, 0, set.length);
            set = temp;
        }
        set[key] = true;
    }

    public void remove(int key) {
        if (key <= set.length - 1) {
            set[key] = false;
        }
    }

    public boolean contains(int key) {
        if (key <= set.length - 1) {
            return set[key];
        }
        return false;
    }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */