705. Design HashSet

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

• void add(key) Inserts the value key into the HashSet.
• bool contains(key) Returns whether the value key exists in the HashSet or not.
• void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

Example 1:

Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]

Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // return False, (already removed)

Constraints:

• $0 <= key <= 10^6$
• At most $10^4$ calls will be made to add, remove, and contains.

Code

450. Delete Node in a BST

class MyHashSet {
    // 每一个bucket中都存了一个BST
    private Bucket[] buckets;
    private int mod;

    public MyHashSet() {
        // 通常选择prime number作为modulo
        this.mod = 769;
        this.buckets = new Bucket[this.mod];
        for (int i = 0; i < this.mod; ++i)
            this.buckets[i] = new Bucket();
    }

    protected int getHash(int key) {
        return (key % this.mod);
    }

    public void add(int key) {
        int bucketIndex = this.getHash(key);
        this.buckets[bucketIndex].insert(key);
    }

    public void remove(int key) {
        int bucketIndex = this.getHash(key);
        this.buckets[bucketIndex].delete(key);
    }

    public boolean contains(int key) {
        int bucketIndex = this.getHash(key);
        return this.buckets[bucketIndex].exists(key);
    }
}

class Bucket {
    private BSTree tree;

    public Bucket() {
        tree = new BSTree();
    }

    public void insert(Integer key) {
        this.tree.root = this.tree.insertIntoBST(this.tree.root, key);
    }

    public void delete(Integer key) {
        this.tree.root = this.tree.deleteNode(this.tree.root, key);
    }

    public boolean exists(Integer key) {
        TreeNode node = this.tree.searchBST(this.tree.root, key);
        return (node != null);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class BSTree {
    TreeNode root = null;

    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || val == root.val) return root;

        return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
    }

    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);

        if (val == root.val) {
            return root;
        } else if (val > root.val) {
            root.right = insertIntoBST(root.right, val);
        } else {
            root.left = insertIntoBST(root.left, val);
        }

        return root;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;

        if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else {
            if(root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                TreeNode min = root.right;
                while(min.left != null) {
                    min = min.left;
                }

                root.val = min.val;
                root.right = deleteNode(root.right, min.val);
            }
        }

        return root;
    }
}

time: O(log(N/K)) space: O(K+M)

class MyHashSet {
    private Bucket[] buckets;
    private int mod;

    public MyHashSet() {
        // 通常选择prime number作为modulo
        this.mod = 769;
        this.buckets = new Bucket[this.mod];
        for (int i = 0; i < this.mod; ++i) {
            this.buckets[i] = new Bucket();
        }
    }

    protected int getHash(int key) {
        return (key % this.mod);
    }

    public void add(int key) {
        int bucketIndex = this.getHash(key);
        this.buckets[bucketIndex].insert(key);
    }

    public void remove(int key) {
        int bucketIndex = this.getHash(key);
        this.buckets[bucketIndex].delete(key);
    }

    public boolean contains(int key) {
        int bucketIndex = this.getHash(key);
        return this.buckets[bucketIndex].exists(key);
    }
}

class Bucket {
    // 当位置确定的时,LinkedList 插入和删除都是O(1)时间
    private LinkedList<Integer> list;

    public Bucket() {
        list = new LinkedList<>();
    }

    public void insert(Integer key) {
        int index = this.list.indexOf(key);
        if (index == -1) {
            this.list.addFirst(key);
        }
    }

    public void delete(Integer key) {
        this.list.remove(key);
    }

    public boolean exists(Integer key) {
        int index = this.list.indexOf(key);
        return (index != -1);
    }
}

假设是平均分布,那么每个 bucket 的大小是 N/K,所以搜索每个 bucket 的时间复杂度是 O(K/N)

time: O(N/K) space: O(K+M)