力扣 (LeetCode)-合并两个有序数组,字典,散列表
前言
❤️笔芯❤️~
栈,队列,链表,集合
字典和散列表
- 集合,字典,散列表可以存储不重复的值
- 在字典中,使用
[键,值]
的形式来存储数据 - 散列表中也是以
[键,值]
对的形式来存储数据 - 字典中键名是用来查询特定元素的
- 字典数据结构的例子,一个实际的字典,以及一个地址簿
创建字典
1 | function Dictionary() { |
使用到的方法:
set(key,value)
,向字典中添加新元素delete(key)
,通过使用键值来从字典中移除键值对应的数据值has(key)
,如果某个键值存在于这个字典中,则返回true,反之则返回falseget(key)
,通过键值查找特定的数值并返回clear()
,将这个字典中的所有元素全部删除size()
,返回字典所包含元素的数量keys()
,将字典所包含的所有键名以数组形式返回values()
,将字典所包含的所有数值以数组形式返回
has
和set
方法
示例:
1 | this.has = function(key) { |
set
方法的实现:
1 | // 将value设为items对象的key属性的值 |
delete
方法
使用JavaScript
的remove
操作符来从items
对象中移除key
属性
1 | this.delete= function(key) { |
get
和values
方法
在字典中查找一个特定的项,并检索它的值
1 | this.get = function(key) { |
以数组的形式返回字典中所有values
实例的值
1 | this.values = function() { |
clear,size,keys,getItems
方法
示例:
1 | this.keys = function() { |
1 | this.getItems = function() { |
使用
Dictionary
类
实现一个电子邮件地址簿:
1 | var dictionary = new Dictionary(); |
散列表
HashTable
类(HashMap
类),它是Dictionary
类的一种散列表实现方式- 如果使用散列函数,就知道值的具体位置,因此能够快速检索到该值
- 散列函数的作用是给定一个键值,然后返回值在表中的地址
创建散列表
1 | // 使用数组来表示我们的数据结构 |
put(key,value)
,向散列表增加一个新的项remove(key)
,根据键值从散列表中移除值get(key)
,返回根据键值检索到的特定的值
示例:
1 | // HashTable类中的一个私有方法 |
实现put
方法
1 | this.put = function(key, value) { |
实现一个get
方法
1 | this.get = function (key) { |
实现一个remove
方法
1 | this.remove = function(key) { |
散列表和散列集合
- 可以使用散列集合来存储所有的英语单词
- 散列集合只存储唯一的不重复的值
- 散列集合由一个集合构成,但是插入、移除或获取元素时,使用的是散列函数
示例:
1 | // 实现print的方法 |
有时候,一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候,我们称其为
冲突。处理冲突有几种方法:分离链接、线性探查和双散列法
示例说明一个:分离链接
分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。
1 | // 在HashTable类内部定义 |
put
方法
1 | this.put = function(key, value){ |
get
方法
1 | this.get = function(key) { |
WeakMap
类和 WeakSet
类
- 弱化版本,
WeakSet和WeakMap
Map和Set
与其弱化版本之间,WeakSet或WeakMap类没有entries、keys和values
等方法- 只能用对象作为键
- 除非你知道键,否则没有办法取出值
简单算法:0001两数之和 👍,0020. 有效的括号 👍,0021. 合并两个有序链表,0026. 删除排序数组中的重复项,0053. 最大子序和,0066. 加一
88. 合并两个有序数组
一、题目描述
给你两个有序整数数组 nums1 和 nums2
,请你将 nums2
合并到 nums1
中,使 nums1
成为一个有序数组。
初始化 nums1 和 nums2
的元素数量分别为 m 和 n
。你可以假设 nums1
的空间大小等于 m + n
,这样它就有足够的空间保存来自 nums2
的元素。
1 | 输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 |
二、思路分析
其实这是一个归并的过程,也是归并排序中最核心的一步。对于两个有序的数组。我们可以新建一个数组temp
,大小为(m+n
)。使用两个指针i和j分别指向nums1和nums2
,之后分别比较两个指针所指元素的大小,并把小的那一个放到temp
中即可。待一个数组遍历完之后,只需将剩下的元素放到temp
中即可。
标签:从后向前数组遍历
因为
nums1
的空间都集中在后面,所以从后向前处理排序的数据会更好,节省空间,一边遍历一边将值填充进去设置指针
len1 和 len2
分别指向nums1 和 nums2
的有数字尾部,从尾部值开始比较遍历,同时设置指针len
指向nums1
的最末尾,每次遍历比较值大小之后,则进行填充当
len1<0
时遍历结束,此时nums2
中获取数据未拷贝完全,将其直接拷贝到nums1
的前面,最后得到结果数组时间复杂度:
O(m+n)O(m+n)
双指针
- 写指针 current, 用于记录当前填补到那个位置了
- m 用于记录 nums1 数组处理到哪个元素了
- n 用于记录 nums2 数组处理到哪个元素了
- 灰色代表 num2 数组已经处理过的元素
- 红色代表当前正在进行比较的元素
- 绿色代表已经就位的元素
三、答案代码
1 | /** |
1 | var merge = function (nums1, m, nums2, n) { |
总结
合并两个有序数组,字典,散列表
回看笔者往期高赞文章,也许能收获更多喔!
- 一个合格的初级前端工程师需要掌握的模块笔记
- Vue.js笔试题解决业务中常见问题
- 【初级】个人分享Vue前端开发教程笔记
- 长篇总结之JavaScript,巩固前端基础
- 前端面试必备ES6全方位总结
- 达达前端个人web分享92道JavaScript面试题附加回答
- 【图文并茂,点赞收藏哦!】重学巩固你的Vuejs知识体系
- 【思维导图】前端开发-巩固你的JavaScript知识体系
- 14期-连肝7个晚上,总结了计算机网络的知识点!(共66条)
- 这是我的第一次JavaScript初级技巧
- localStorage和sessionStorage本地存储
- HTML5中的拖放功能
- 挑战前端知识点HTTP/ECMAScript
- 必学必会-音频和视频
- 前端170面试题+答案学习整理(良心制作)
- 前端HTML5面试官和应试者一问一答
- 哪吒闹海,席卷图文学习前端Flex布局
- 腾讯位置服务开发应用
- 【进阶】面试官问我Chrome浏览器的渲染原理(6000字长文)
- 面试官一上来就问我Chrome底层原理和HTTP协议(万字长文)
- 熬夜总结了 “HTML5画布” 的知识点
- this/call/apply/bind(万字长文)
- HTTP/HTTPS/HTTP2/DNS/TCP/经典题
- 执行上下文/作用域链/闭包/一等公民
- Web页面制作基础
- 学习总结之HTML5剑指前端(建议收藏,图文并茂)
❤️关注+点赞+收藏+评论+转发❤️,原创不易,鼓励笔者创作更好的文章