Formatted question description: https://leetcode.ca/all/705.html

705. Design HashSet

Level

Easy

Description

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

To be specific, your design should include these functions:

  • add(value): Insert a value into the HashSet.
  • contains(value): Return whether the value exists in the HashSet or not.
  • remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.

Example:

MyHashSet hashSet = new MyHashSet();
hashSet.add(1);         
hashSet.add(2);         
hashSet.contains(1);    // returns true
hashSet.contains(3);    // returns false (not found)
hashSet.add(2);          
hashSet.contains(2);    // returns true
hashSet.remove(2);          
hashSet.contains(2);    // returns false (already removed)

Note:

  • All values will be in the range of [0, 1000000].
  • The number of operations will be in the range of [1, 10000].
  • Please do not use the built-in HashSet library.

Solution

Since all values are in the range of [0, 1000000], create an array with length 1000001, which has boolean type.

If a value is added, set the element at the corresponding index in the array to true. If a value is removed, set the element at the corresponding index in the array to false.

For the contains function, simply return the element at the corresponding index in the array, where true means the element exists in the HashSet and false means the element does not exist in the HashSet.

public class Design_HashSet {


    class MyHashSet {

        boolean[] set;

        /** Initialize your data structure here. */
        public MyHashSet() {
            set = new boolean[1000001];
        }

        public void add(int key) {
            set[key]=true;
        }

        public void remove(int key) {
            set[key]=false;
        }

        /** Returns true if this set contains the specified element */
        public boolean contains(int key) {
            return set[key];
        }

    }

    // wrong solution...
    class MyHashSet {
            boolean[][] set;

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

            public void add(int key) {
                set[key%1000][(key%1000)/1000] = true;
            }

            public void remove(int key) {
                set[key%1000][(key%1000)/1000] = false;
            }

            /** Returns true if this set contains the specified element */
            public boolean contains(int key) {
                return set[key%1000][(key%1000)/1000];
            }    
    }
/**
 * 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);
 */
}

All Problems

All Solutions