MENU

LeetCode350. Intersection of Two Arrays II(模拟)

2019 年 02 月 14 日 • 阅读: 945 • LeetCode阅读设置

LeetCode350. Intersection of Two Arrays II(模拟)

  • Easy
  • Accepted:173,451
  • Submissions:372,710

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?

链接

https://leetcode.com/problems/intersection-of-two-arrays-ii/

题意

给定两个数组,找出它们的交集。集合中元素出现的次数和在两个数组中一样,顺序可以不同。而之前的那道题LeetCode349. Intersection of Two Arrays(模拟)严格意义上来讲是求公共元素。

题解

  • 直接模拟即可,因为元素为多个,所以使用map来完成,写法多样。

代码

  • Runtime: 12 ms, faster than 86.50% of C++ online submissions for Intersection of Two Arrays II.
  • Memory Usage: 9.3 MB, less than 100.00% of C++ online submissions for Intersection of Two Arrays II.
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        map <int, int> mp;
        vector <int> vt;
        for (int i = 0; i < n; ++i)
            mp[nums1[i]]++;
        for (int i = 0; i < m; ++i)
        {
            if (mp.count(nums2[i]) > 0 && mp[nums2[i]] > 0) // 找到且数量大于0
            {
                vt.push_back(nums2[i]);
                mp[nums2[i]]--;
            }
        }
        return vt;
    }
};

没想到整个还WA了一发,mp[nums2[i]]--只能让map中的元素的值减减,而不是删除一个元素,这里要弄清楚,所以还要加一个大于0的条件,直接使用mp[nums2[i]] > 0这个判断就好了,count是用来记录元素出现的个数。

  • 当数组有序时,可以这么写
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        int pt0 = 0, pt1 = 0;
        vector <int> vt;
        while (pt0 < n && pt1 < m)
        {
            if (nums1[pt0] == nums2[pt1]) // 相等时均右移,否则小的先往后移
            {
                vt.push_back(nums1[pt0]);
                ++pt0, ++pt1;
            }
            else if (nums1[pt0] > nums2[pt1])
                pt1++;
            else
                pt0++;
        }
        return vt;
    }
};

The end.
2019年2月14日 星期四