705. Design HashSet - Easy

前往題目

想法

• 和hashmap異曲同工之妙

思路

簡單版:和hashmap那題一樣用同樣大小的array

進階版:也和hashmap那題一樣，用ListNode和chaining

Code

簡單版

class MyHashSet {
    boolean[] set;

    public MyHashSet() {
        set = new boolean[1000001];
        Arrays.fill(set, false);
    }
    
    public void add(int key) {
        set[key] = true;
    }
    
    public void remove(int key) {
        set[key] = false;
    }
    
    public boolean contains(int key) {
        return set[key];
    }
}

TLE

不懂為何TLE，題目不是就要求這種解法嗎

class MyHashSet {
    private class ListNode{
        int key;
        ListNode next;

        public ListNode(){

        }
        public ListNode(int key, ListNode next) {
            this.key = key;
            this.next = next;
        }
    }

    ListNode[] set;

    public MyHashSet() {
        set = new ListNode[1000];
        Arrays.fill(set, new ListNode());
    }

    private int hash(int key) {
        return key % set.length;
    }
    
    public void add(int key) {
        ListNode cur = set[hash(key)];

        while (cur != null && cur.next != null) {
            if (cur.next.key == key) {
                return;
            }
            // Update pointer
            cur = cur.next;
        }
        // Not found, adding
        cur.next = new ListNode(key, null);
    }
    
    public void remove(int key) {
        ListNode cur = set[hash(key)];

        while (cur != null && cur.next != null) {
            // Found, removing
            if (cur.next.key == key) {
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
    }
    
    public boolean contains(int key) {
        ListNode cur = set[hash(key)].next;

        while (cur != null) {
            // Found
            if (cur.key == key) return true;
        }
        // Not found
        return false;
    }
}