LeetCode-706. 设计哈希映射【设计 数组 哈希表 链表 哈希函数】

LeetCode-706. 设计哈希映射【设计 数组 哈希表 链表 哈希函数】

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

题目描述:

不使用任何内建的哈希表库设计一个哈希映射(HashMap)。

实现 MyHashMap 类:

MyHashMap() 用空映射初始化对象
void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中,则更新其对应的值 value 。
int get(int key) 返回特定的 key 所映射的 value ;如果映射中不包含 key 的映射,返回 -1 。
void remove(key) 如果映射中存在 key 的映射,则移除 key 和它所对应的 value 。

示例:

输入:
[“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”, “get”]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出:
[null, null, null, 1, -1, null, 1, null, -1]

解释:
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1); // 返回 1 ,myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3); // 返回 -1(未找到),myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]](更新已有的值)
myHashMap.get(2); // 返回 1 ,myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据,myHashMap 现在为 [[1,1]]
myHashMap.get(2); // 返回 -1(未找到),myHashMap 现在为 [[1,1]]

提示:

0 <= key, value <= 106
最多调用 104 次 put、get 和 remove 方法

此题解法与LeetCode-705. 设计哈希集合【设计 数组 哈希表 链表 哈希函数】非常相似!

解题思路一:超大数组

class MyHashMap:

    def __init__(self):
        self.map = [-1] * 1000001

    def put(self, key: int, value: int) -> None:
        self.map[key] = value

    def get(self, key: int) -> int:
        return self.map[key]

    def remove(self, key: int) -> None:
        self.map[key] = -1

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

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

解题思路二:拉链法

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

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

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

class MyHashMap:

    def __init__(self):
        self.buckets = 1000
        self.table = [[] for _ in range(self.buckets)]

    def hash(self, key):
        return key % self.buckets

    def put(self, key: int, value: int) -> None:
        hashkey = self.hash(key)
        for item in self.table[hashkey]:
            if item[0] == key:
                item[1] = value
                return
        self.table[hashkey].append([key, value])

    def get(self, key: int) -> int:
        hashkey = self.hash(key)
        for item in self.table[hashkey]:
            if item[0] == key:
                return item[1]
        return -1

    def remove(self, key: int) -> None:
        hashkey = self.hash(key)
        for i, item in enumerate(self.table[hashkey]):
            if item[0] == key:
                self.table[hashkey].pop(i)
                return

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

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

解题思路三:

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

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

class MyHashMap(object):

    def __init__(self):
        self.map = [[-1] * 1000 for _ in range(1001)]

    def put(self, key, value):
        row, col = key // 1000, key % 1000
        self.map[row][col] = value

    def get(self, key):
        row, col = key // 1000, key % 1000
        return self.map[row][col]

    def remove(self, key):
        row, col = key // 1000, key % 1000
        self.map[row][col] = -1

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/547042.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SpringBoot基于RabbitMQ实现消息延迟队列方案

知识小科普 在此之前&#xff0c;简单说明下基于RabbitMQ实现延时队列的相关知识及说明下延时队列的使用场景。 延时队列使用场景 在很多的业务场景中&#xff0c;延时队列可以实现很多功能&#xff0c;此类业务中&#xff0c;一般上是非实时的&#xff0c;需要延迟处理的&a…

【讲解下常见的Web前端框架】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

Linux-管道

目录 无名管道关闭未使用的管道文件描述符 管道对应的内存大小与shell命令进行通信&#xff08;popen&#xff09;命名管道FIFO创建FIFO文件打开FIFO文件 无名管道 管道是最早出现的进程间通信的手段。 管道的作用是在有亲缘关系的进程之间传递消息。所谓有亲缘关系&#xff…

【YOLOV5 入门】——Pyside6/PyQt5可视化UI界面后端逻辑

声明&#xff1a;笔记是做项目时根据B站博主视频学习时自己编写&#xff0c;请勿随意转载&#xff01; 一、环境安装 VScode/Pycharm终端进入虚拟环境后&#xff0c;输入下面代码安装pyside6&#xff0c;若用的Pycharm作为集成开发环境&#xff0c;也下载个pyqt5&#xff1a; …

移动Web学习07-适配单位vw/vh哔哩哔哩移动端vw单位适配案例

1.1、VW相对单位 前面我们已经学习了rem单位 &#xff0c;他是一个相对单位、相对于HTML表格字号大小 VW/VH也是一个相对单位&#xff0c;他是相对于视口的尺寸计算结果 VW&#xff1a;viewport width VH: viewport height <meta name"viewport" content"…

C语言之探秘:访问结构体空指针与结构体空指针的地址的区别(九十三)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

华为HarmonyOS 4.2公测升级计划扩展至15款新机型

华为近日宣布&#xff0c;HarmonyOS 4.2操作系统的公测升级计划将扩展到包括华为P50系列在内的15款设备。这一更新旨在为用户提供更优化的系统性能和增强的功能。 参与此次公测的机型包括华为P50、华为P50 Pro及其典藏版、华为P50E、华为P50 Pocket及其艺术定制版、华为nova系…

学习STM32第十四天

软件SPI读写W25Q64 一、简介 对W25Q64模块进行读写操作时&#xff0c;输出引脚配置为推挽输出&#xff0c;输入引脚配置为浮空或上拉输入。时钟、主机输出和片选都是输出引脚&#xff0c;主机输入是输入引脚。SPI协议是通过命令和数据进行通信&#xff0c;在硬件中使用移位寄…

将自己的项目上传至Git

一、安装Git 官网:Git (git-scm.com) 二、注册gitee 官网:工作台 - Gitee.com 进入“我的”出现以下界面 三、创建仓库 点击加号&#xff0c;新建仓库 根据自己的需求取名&#xff0c;描述仓库&#xff0c;开源还是私有&#xff0c;点击创建即可&#xff0c;点击我的即可…

每日一题 — 找到字符串中所有字母异位词

解法一&#xff1a;暴力枚举 解法二&#xff1a;滑动窗口hash表优化 定义left和right为起始坐标0&#xff0c;right向后遍历&#xff0c;并加入到哈希表中&#xff0c;然后也要记录下来每次进入哈希表的有效字符&#xff08;与目标字符串中相同的字符&#xff09;的个数且这个滑…

C++修炼之路之list模拟实现--C++中的双向循环链表

目录 引言 一&#xff1a;STL源代码中关于list的成员变量的介绍 二&#xff1a;模拟实现list 1.基本结构 2.普通迭代器 const迭代器的结合 3.构造拷贝构造析构赋值重载 清空 4.inserterase头尾插入删除 5.打印不同数据类型的数据《使用模板加容器来完成》 三&#xf…

SQLite、MySQL 和 PostgreSQL 数据库速度比较(本文阐述时间很早比较,不具有最新参考性)(二十五)

返回&#xff1a;SQLite—系列文章目录 上一篇&#xff1a;用于 SQLite 的异步 I/O 模块&#xff08;二十四&#xff09; 下一篇&#xff1a;SQLite—系列文章目录 注意&#xff1a;本文档非常非常旧。它描述了速度比较 SQLite、MySQL 和 PostgreSQL 的古老版本。 这里…

学习一门语言的方法和套路(B站转述)

视频链接 up虽然长相英(ping)俊(ping)&#xff0c;但是讲的干活&#xff0c;没恰饭。 学习流程&#xff1a; 1.快速阅读&#xff0c;掌握概况 2.深入细节内容 例如&#xff1a;java (JDBC)、html 、netty 不管三七二十一&#xff0c;先了解套路&#xff0c;再深入研究。 高…

安装CUDNN详细过程

cuDNN&#xff08;CUDA Deep Neural Network library&#xff09;是由NVIDIA开发的深度学习GPU加速库。 cuDNN包含了许多针对神经网络操作进行高度优化的函数&#xff0c;旨在使深度学习框架能够在NVIDIA的GPU上实现最佳性能&#xff0c;这个库提供了高效计算和加速&#xff0c…

牛客网刷题 :BC50 你是天才吗

描述 据说智商140以上者称为天才&#xff0c;KiKi想知道他自己是不是天才&#xff0c;请帮他编程判断。输入一个整数表示一个人的智商&#xff0c;如果大于等于140&#xff0c;则表明他是一个天才&#xff0c;输出“Genius”。 输入描述&#xff1a; 多组输入&#xff0c;每…

在 PyCharm 中使用系统安装的 Python 和 Anaconda 的 Python什么区别

virtualenv environment &#xff1a; virtualenv 是一个用于创建独立 Python 环境的工具。它可以在同一个系统上创建多个相互独立的 Python 环境&#xff0c;每个环境都有自己的 Python 解释器和包库&#xff0c;从而可以实现不同项目之间的依赖隔离和版本控制。coda environm…

vue快速入门(二十五)本地存储与初始化使用

注释很详细&#xff0c;直接上代码 上一篇 新增内容 本地获取数据数据存储到本地 源码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial…

2024蓝桥杯——宝石问题

先展示题目 声明 以下代码仅是我的个人看法&#xff0c;在自己考试过程中的优化版&#xff0c;本人考试就踩了很多坑&#xff0c;我会—一列举出来。代码可能很多&#xff0c;但是总体时间复杂度不高只有0(N) 函数里面的动态数组我没有写开辟判断和free&#xff0c;这里我忽略…

频率域滤波基础(离散傅里叶变换使用填充的缺陷)

本来是个很简单的问题&#xff0c;作者硬是写的这么复杂&#xff0c;翻译还搞错了。重点是我发现作者真正有用的东西没讲到&#xff0c;比如相位和谱如何影响图像。连个转换公式都没有&#xff0c;我只能说作者是在混字数。 首先看关于中心对称是什么意思&#xff1f;我木太明白…

MySql 视图 存储过程 触发器

文章目录 视图数据库对象视图的理解创建、查看、更新、删除 存储过程和存储函数概述分类存储过程的创建和调用存储函数的创建和调用存储过程和存储函数的对比存储过程和存储函数的查看、修改、删除 变量GLOBAL 与 SESSION 变量的使用会话用户变量和局部变量的使用 定义条件与处…