leetCode 350. Intersection of Two Arrays II 哈希

简介:

350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1]nums2 = [2, 2], return [2, 2].

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?

题目大意:

找出两个数组中相同元素,相同元素的个数可以大于1.

思路:

将数组2的元素放入multiset中。

遍历数组1,如果在multiset找到与数组1相等的元素,将该元素放入结果数组中,在multiset中删除第一个和这个元素相当的元素。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class  Solution {
public :
     vector< int > intersect(vector< int >& nums1, vector< int >& nums2) {
         vector< int > result;
         multiset< int > set2;
         for ( int  i = 0; i < nums2.size(); i++)
             set2.insert(nums2[i]);
         for ( int  i = 0; i < nums1.size(); i++)
         {
             if (set2.find(nums1[i]) != set2.end())
             {
                 result.push_back(nums1[i]);
                 set2.erase(set2.find(nums1[i]));
             }
         }
         return  result;
     }
};



本文转自313119992 51CTO博客,原文链接:http://blog.51cto.com/qiaopeng688/1837559
相关文章
|
30天前
《LeetCode》—— 哈希
《LeetCode》—— 哈希
|
30天前
leetcode-1044:最长重复子串(滚动哈希)
leetcode-1044:最长重复子串(滚动哈希)
34 0
|
9月前
|
存储 缓存 算法
LeetCode刷题---Two Sum(一)
LeetCode刷题---Two Sum(一)
|
5天前
|
存储 SQL 算法
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
|
5天前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
30天前
[leetcode] 705. 设计哈希集合
[leetcode] 705. 设计哈希集合
|
30天前
leetcode-1001:网格照明(自定义哈希集合)
leetcode-1001:网格照明(自定义哈希集合)
22 0
|
7月前
Leetcode 4. Median of Two Sorted Arrays
题目描述很简单,就是找到两个有序数组合并后的中位数,要求时间复杂度O(log (m+n))。 如果不要去时间复杂度,很容易就想到了归并排序,归并排序的时间复杂度是O(m+n),空间复杂度也是O(m+n),不满足题目要求,其实我开始也不知道怎么做,后来看了别人的博客才知道有个二分法求两个有序数组中第k大数的方法。
18 0
|
9月前
|
存储 C++ Python
LeetCode刷题---Add Two Numbers(一)
LeetCode刷题---Add Two Numbers(一)
|
12月前
|
存储 算法 安全
LeetCode - #2 Add Two Numbers
我们社区从本期开始会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。
LeetCode - #2 Add Two Numbers