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

相关文章

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

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

Kotlin 作用域函数apply、let、run、with、also使用指南

《Kotlin作用域函数apply、let、run、with、also使用指南》在Kotlin开发中,作用域函数(ScopeFunctions)是一组能让代码更简洁、更函数式的高阶函数,本文将... 目录一、引言:为什么需要作用域函数?二、作用域函China编程数详解1. apply:对象配置的 “流式构建器”最

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

kotlin的函数forEach示例详解

《kotlin的函数forEach示例详解》在Kotlin中,forEach是一个高阶函数,用于遍历集合中的每个元素并对其执行指定的操作,它的核心特点是简洁、函数式,适用于需要遍历集合且无需返回值的场... 目录一、基本用法1️⃣ 遍历集合2️⃣ 遍历数组3️⃣ 遍历 Map二、与 for 循环的区别三、高

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》:本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表(List) - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典(D

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

MySQL中COALESCE函数示例详解

《MySQL中COALESCE函数示例详解》COALESCE是一个功能强大且常用的SQL函数,主要用来处理NULL值和实现灵活的值选择策略,能够使查询逻辑更清晰、简洁,:本文主要介绍MySQL中C... 目录语法示例1. 替换 NULL 值2. 用于字段默认值3. 多列优先级4. 结合聚合函数注意事项总结C