LeetCode Notes_#705_设计哈希集合

LeetCode Notes_#705_设计哈希集合

LeetCode

Contents

题目

思路分析

其实很简单,但是函数比较多,看起来有些麻烦,需要提前设计好各个函数的返回值,参数等,互相配合使用。
核心思路:
将数据根据散列函数(或者叫做哈希函数),存储到不同的“桶”当中,做任何操作的时候,先找到对应的桶(相当于缩小范围),然后在桶里进行操作。

解答

class MyHashSet {
    private Bucket[] bucketArray;
    private int bucketNum;

    /** Initialize your data structure here. */
    public MyHashSet() {
        bucketNum = 769;
        bucketArray = new Bucket[bucketNum];
        for(int i = 0;i <= bucketNum - 1;i++){
            bucketArray[i] = new Bucket();
        }
    }

    private int hash(int key){
        return key % bucketNum;
    }
    
    public void add(int key) {
        int bucketIndex = hash(key);
        bucketArray[bucketIndex].bucket_add(key);
    }
    
    public void remove(int key) {
        int bucketIndex = hash(key);
        bucketArray[bucketIndex].bucket_remove(key);
    }
    
    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        int bucketIndex = hash(key);
        return bucketArray[bucketIndex].bucket_contains(key);
    }
}

class Bucket{
    private LinkedList<Integer> bucket;

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

    //方法设置为public是因为要被MyHashSet类所调用
    public void bucket_add(int key){
        //如果桶里没有相应的key,那么就将其插入到桶里;如果已经包含了key,就不插入
        if(!bucket_contains(key)) bucket.addFirst(key);
    }

    public void bucket_remove(int key){
        int key_index = bucket.indexOf(key);
        if(key_index != -1) bucket.remove(key_index);
    }

    public boolean bucket_contains(int key){
        int index = bucket.indexOf(key);
        return index != -1;
    }
}

复杂度分析

时间复杂度:O(N/K),N是所有键值对的数量,K是桶的数量
空间复杂度:O(K+M),K是桶的数量,M是已经插入的键值对的数量

上一篇:LeetCode Notes_#705_设计哈希集合


下一篇:2020 Cybrics CTF Web Writeup