LeetCode 350. Intersection of Two Array

本文主要是介绍LeetCode 350. Intersection of Two Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

350. Intersection of Two Array

一、问题描述

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

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?

二、输入输出

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

三、解题思路

和之前找交叉的那道题不同之处在于，这里需要按照具体出现了几次都输出出来。个人想法很直，把两个数组分别存储到一个map中，记录下每个元素出现的次数。假设一共有n个元素，那么时间复杂度是o(n) map的实现是红黑树，插入的复杂度是o(logn)。然后遍历这两个map找到相同的元素，取出现的个数较小的那个作为最终结果存储到vector中返回。

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {map<int, int> dict1, dict2;int n1 = nums1.size(), n2 = nums2.size();for (int i = 0; i < n1; ++i) {if(dict1.find(nums1[i]) == dict1.end()) dict1.insert(make_pair(nums1[i], 1));else dict1[nums1[i]]++;}for (int j = 0; j < n2; ++j) {if(dict2.find(nums2[j]) == dict2.end()) dict2.insert(make_pair(nums2[j], 1));else dict2[nums2[j]]++;}vector<int> ret;for (auto ite : dict1){int key = ite.first;int cnt = 0;map<int, int>::iterator ite2;if((ite2 = dict2.find(key)) != dict2.end()){cnt = min(ite.second, ite2->second);}for (int i = 0; i < cnt; ++i) {ret.push_back(key);}}return ret;}
};