Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1's size is small compared to nums2's size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
解法一:
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> m;
vector<int> res;
for (auto a : nums1) ++m[a];
for (auto a : nums2) {
if (m[a]-- > ) res.push_back(a);
}
return res;
}
};
再来看一种方法,这种方法先给两个数组排序,然后用两个指针分别指向两个数组的起始位置,如果两个指针指的数字相等,则存入结果中,两个指针均自增1,如果第一个指针指的数字大,则第二个指针自增1,反之亦然,参见代码如下:
解法二:
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
int i = , j = ;
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i] == nums2[j]) {
res.push_back(nums1[i]);
++i; ++j;
} else if (nums1[i] > nums2[j]) {
++j;
} else {
++i;
}
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/350
类似题目:
Find Common Characters
参考资料:
https://leetcode.com/problems/intersection-of-two-arrays-ii/
https://leetcode.com/problems/intersection-of-two-arrays-ii/discuss/82269/Short-Python-C%2B%2B
[LeetCode] 350. Intersection of Two Arrays II 两个数组相交之二的更多相关文章
-
[LeetCode] 350. Intersection of Two Arrays II 两个数组相交II
Given two arrays, write a function to compute their intersection. Example 1: Input: nums1 = [1,2,2,1 ...
-
[LintCode] Intersection of Two Arrays II 两个数组相交之二
Given two arrays, write a function to compute their intersection.Notice Each element in the result s ...
-
[LeetCode] Intersection of Two Arrays II 两个数组相交之二
Given two arrays, write a function to compute their intersection. Example:Given nums1 = [1, 2, 2, 1] ...
-
350 Intersection of Two Arrays II 两个数组的交集 II
给定两个数组,写一个方法来计算它们的交集.例如:给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].注意: 输出结果中每个元素出现的次数, ...
-
26. leetcode 350. Intersection of Two Arrays II
350. Intersection of Two Arrays II Given two arrays, write a function to compute their intersection. ...
-
LeetCode 350. Intersection of Two Arrays II (两个数组的相交之二)
Given two arrays, write a function to compute their intersection. Example:Given nums1 = [1, 2, 2, 1] ...
-
LeetCode 350. Intersection of Two Arrays II
Given two arrays, write a function to compute their intersection. Example:Given nums1 = [1, 2, 2, 1] ...
-
Python [Leetcode 350]Intersection of Two Arrays II
题目描述: Given two arrays, write a function to compute their intersection. Example:Given nums1 = [1, 2, ...
-
LeetCode 349. Intersection of Two Arrays (两个数组的相交)
Given two arrays, write a function to compute their intersection. Example:Given nums1 = [1, 2, 2, 1] ...
随机推荐
-
iNeedle系统之国舜项目
一.简介 本周公司接了一个小项目,是给北京国舜科技股份有限公司做一个HTTP相关的小功能产品.大概实现功能是将交换机的源数据通过解析,分析出HTTP包配对的request和response头,并把每对 ...
-
java读写excel文件
近期处理的数据规模比较大,正好又是统计合并的事情,想着借助excel就可以完成了,然后就了解了下java读取excel的事情. 读取的文件主要分两类:xls文件.xlsx文件.xls文件的相关操作用的 ...
-
CSS3_标准盒子模型和怪异盒子模型
#box{ width: 200px; height: 200px; background-color: pink; } 标准盒子模型 box-sizing: content-box; padding ...
-
VirtualBox安装linux
VBox相较于VMware要小巧,虚拟机该有的都有了.搭建记录下,学习... centos版本:CentOS-6.6-i386-bin-DVD1 VBox版本:6.0.4-128413-Win 之后可 ...
-
通过反编译深入理解Java String及intern
一.字符串问题 字符串在我们平时的编码工作中其实用的非常多,并且用起来也比较简单,所以很少有人对其做特别深入的研究.倒是面试或者笔试的时候,往往会涉及比较深入和难度大一点的问题.我在招聘的时候也偶尔会 ...
-
使用hive分析nginx访问日志方法
以下案例是使用hive分析nginx的访问日志案例,其中字段分隔通过正则表达式匹配,具体步骤如下: 日志格式: 192.168.5.139 - - [08/Jun/2017:17:09:12 +080 ...
-
Gitolite 权限控制
官网 http://gitolite.com/gitolite/index.html 安装配置 http://gitolite.com/gitolite/install/ 傻瓜安装教程 http:// ...
-
sqoop快速入门
转自http://www.aboutyun.com/thread-22549-1-1.html
-
JAVAEE——SSH项目实战01:SVN介绍、eclipse插件安装和使用方法
1 学习目标 1.掌握svn服务端.svn客户端.svn eclipse插件安装方法 2.掌握svn的基本使用方法 2 svn介绍 2.1 项目管理中的版本控制问题 通常软件开发由多人协作开发,如果对 ...
-
glsl Dream
<-vertex-> #version varying vec2 uv; void main(void) { uv = gl_MultiTexCoord0.st; gl_Position ...