哈希表|349.两个数组的交集

2024-03-11 18:52
文章标签 数组 哈希 两个 交集 349

本文主要是介绍哈希表|349.两个数组的交集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

力扣题目链接

int* intersection1(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int nums1Cnt[1000] = {0};int lessSize = nums1Size < nums2Size ? nums1Size : nums2Size;int * result = (int *) calloc(lessSize, sizeof(int));int resultIndex = 0;int* tempNums;int i;/* Calculate the number's counts for nums1 array */for(i = 0; i < nums1Size; i ++) {nums1Cnt[nums1[i]]++;}/* Check if the value in nums2 is existing in nums1 count array */for(i = 0; i < nums2Size; i ++) {if(nums1Cnt[nums2[i]] > 0) {result[resultIndex] = nums2[i];resultIndex ++;/* Clear this count to avoid duplicated value */nums1Cnt[nums2[i]] = 0;}}* returnSize = resultIndex;return result;
}

有些地方一开始没理解,突然看着看着就理解了。

自己写起来总是考虑不好呜呜呜!

一、出错点

1.为考虑到存放相同字母的rusult

2.一开始不理解第二个for循环

二、理解后的思路

calloc也是分配内存空间,它和malloc的区别就是它可以分配空间后都初始化为0.

代码随想录 (programmercarl.com)

这道题目,主要要学会使用一种哈希数据结构:unordered_set,这个数据结构可以解决很多类似的问题。

注意题目特意说明:输出结果中的每个元素一定是唯一的,也就是说输出的结果的去重的, 同时可以不考虑输出结果的顺序

这道题用暴力的解法时间复杂度是O(n^2),那来看看使用哈希法进一步优化。

那么用数组来做哈希表也是不错的选择,例如242. 有效的字母异位词(opens new window)

但是要注意,使用数组来做哈希的题目,是因为题目都限制了数值的大小。

而这道题目没有限制数值的大小,就无法使用数组来做哈希表了。

而且如果哈希值比较少、特别分散、跨度非常大,使用数组就造成空间的极大浪费。

此时就要使用另一种结构体了,set ,关于set,C++ 给提供了如下三种可用的数据结构:

  • std::set
  • std::multiset
  • std::unordered_set

std::set和std::multiset底层实现都是红黑树,std::unordered_set的底层实现是哈希表, 使用unordered_set 读写效率是最高的,并不需要对数据进行排序,而且还不要让数据重复,所以选择unordered_set。

思路如图所示:

set哈希法

这是卡哥的思路,我自己现在之后用数组的方式。

就是它存在相同的,就用数组保存,最后返回结果。 

三、总结

多看一下库函数,混个眼熟。

多做题目,多看代码,多自己独立敲代码!

这篇关于哈希表|349.两个数组的交集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

Java如何将文件内容转换为MD5哈希值

《Java如何将文件内容转换为MD5哈希值》:本文主要介绍Java如何将文件内容转换为MD5哈希值的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java文件内容转换为MD5哈希值一个完整的Java示例代码代码解释注意事项总结Java文件内容转换为MD5

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数组获取数组的长度读取某下的