LeetCode-705. 设计哈希集合【设计 数组 哈希表 链表 哈希函数】

2024-04-15 05:20

本文主要是介绍LeetCode-705. 设计哈希集合【设计 数组 哈希表 链表 哈希函数】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LeetCode-705. 设计哈希集合【设计 数组 哈希表 链表 哈希函数】

  • 题目描述:
  • 解题思路一:超大数组
  • 解题思路二:拉链法
  • 解题思路三:定长拉链数组

题目描述:

不使用任何内建的哈希表库设计一个哈希集合(HashSet)。

实现 MyHashSet 类:

void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。

示例:

输入:
[“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”, “remove”, “contains”]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出:
[null, null, null, true, false, null, true, null, false]

解释:
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ,(未找到)
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // 返回 False ,(已移除)

提示:

0 <= key <= 106
最多调用 104 次 add、remove 和 contains

解题思路一:超大数组

class MyHashSet:def __init__(self):self.set = [False] * 1000001def add(self, key: int) -> None:self.set[key] = Truedef remove(self, key: int) -> None:self.set[key] = Falsedef contains(self, key: int) -> bool:return self.set[key]# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)

时间复杂度:O(1)
空间复杂度:O(数据范围)

解题思路二:拉链法

在这里插入图片描述
不定长的拉链数组是说拉链会根据分桶中的 key 动态增长,更类似于真正的链表。

分桶数一般取质数,这是因为经验上来说,质数个的分桶能让数据更加分散到各个桶中。

优点:节省内存,不用预知数据范围;
缺点:在链表中查找元素需要遍历。

class MyHashSet:def __init__(self):self.buckets = 1009self.table = [[] for _ in range(self.buckets)]def hash(self, key):return key % self.bucketsdef add(self, key: int) -> None:hashkey = self.hash(key)if key in self.table[hashkey]:returnself.table[hashkey].append(key)def remove(self, key: int) -> None:hashkey = self.hash(key)if key not in self.table[hashkey]:returnself.table[hashkey].remove(key)def contains(self, key: int) -> bool:hashkey = self.hash(key)return key in self.table[hashkey]

时间复杂度:O(N/b) N 是元素个数,b 是桶数。
空间复杂度:O(N)

解题思路三:定长拉链数组

这个方法本质上就是把 HashSet 设计成一个 M∗N 的二维数组。第一个维度用于计算 hash 分桶,第二个维度寻找 key 存放具体的位置。用了一个优化:第二个维度的数组只有当需要构建时才会产生,这样可以节省内存。

优点:两个维度都可以直接计算出来,查找和删除只用两次访问内存。
缺点:需要预知数据范围,用于设计第二个维度的数组大小。

class MyHashSet:def __init__(self):self.buckets = 1000self.itemsPerBucket = 1001self.table = [[] for _ in range(self.buckets)]def hash(self, key):return key % self.bucketsdef pos(self, key):return key // self.bucketsdef add(self, key):hashkey = self.hash(key)if not self.table[hashkey]:self.table[hashkey] = [0] * self.itemsPerBucketself.table[hashkey][self.pos(key)] = 1def remove(self, key):hashkey = self.hash(key)if self.table[hashkey]:self.table[hashkey][self.pos(key)] = 0def contains(self, key):hashkey = self.hash(key)return (self.table[hashkey] != []) and (self.table[hashkey][self.pos(key)] == 1)

时间复杂度:O(1)
空间复杂度:O(数据范围)

这篇关于LeetCode-705. 设计哈希集合【设计 数组 哈希表 链表 哈希函数】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/904937

相关文章

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI

MySQL中FIND_IN_SET函数与INSTR函数用法解析

《MySQL中FIND_IN_SET函数与INSTR函数用法解析》:本文主要介绍MySQL中FIND_IN_SET函数与INSTR函数用法解析,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一... 目录一、功能定义与语法1、FIND_IN_SET函数2、INSTR函数二、本质区别对比三、实际场景案例分

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,:本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例:2. strerror()示例:3. perror(