专栏首页木又AI帮【leetcode刷题】T44-两个数组的交集 II

【leetcode刷题】T44-两个数组的交集 II

【英文题目】(学习英语的同时,更能理解题意哟~)

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

Example 1:

Input: nums1 = [,,,], nums2 = [,]
Output: [,]

Example 2:

Input: nums1 = [,,], nums2 = [,,,,]
Output: [,]

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

【中文题目】

给定两个数组,编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [,,,], nums2 = [,]
输出: [,]

示例 2:

输入: nums1 = [,,], nums2 = [,,,,]
输出: [,]

说明:

  • 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
  • 我们可以不考虑输出结果的顺序。

【思路】

使用字典/map 对所有元素进行计数,将共同元素存入结果中,重复次数为两个数组中该元素出现次数最小值。

【代码】

python版本

class Solution(object):
    def get_dict(self, nums):
        d = {}
        for n in nums:
            d[n] = d.get(n, ) + 
        return d

    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        d1 = self.get_dict(nums1)
        d2 = self.get_dict(nums2)
        res = []
        for k, v1 in d1.items():
            if k in d2:
                # 元素个数较小值
                res.extend([k] * min(v1, d2[k]))
        return res

C++版本

class Solution {
public:
    map<int, int> get_map(vector<int>& num){
        map<int, int> d;
        for(int i=; i<num.size(); i++){
            d[num[i]]++;
        }
        return d;
    }

    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> d1 = get_map(nums1);
        map<int, int> d2 = get_map(nums2);
        vector<int> res;
        for(map<int, int>::iterator it=d1.begin(); it != d1.end(); it++){
            if(d2.find(it->first) != d2.end()){
                int times = min(it->second, d2[it->first]);
                for(int j=; j<times; j++)
                    res.push_back(it->first);
            }
        }
        return res;
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T159-爬楼梯

    https://leetcode-cn.com/problems/climbing-stairs/

    木又AI帮
  • 【leetcode刷题】T34-只出现一次的数字 II

    Given a non-empty array of integers, every element appears three times except fo...

    木又AI帮
  • 【leetcode刷题】T53-错误的集合

    集合 S 包含从1到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个元素复制了成了集合里面的另外一个元素的值,导致集合丢失了一个整数并且有一个元素重复。

    木又AI帮
  • loj#6073. 「2017 山东一轮集训 Day5」距离(费用流)

    我们可以把图行列拆开,同时对于行/列拆成很多个联通块,然后考虑每个点所在的行联通块/列联通块的贡献。

    attack
  • 13:大整数的因子

    13:大整数的因子 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 已知正整数k满足2<=k<=9,现给出长度最大为30位...

    attack
  • 洛谷P2881 [USACO07MAR]排名的牛Ranking the Cows(bitset Floyd)

    显然如果题目什么都不说的话需要\(\frac{n * (n - 1)}{2}\)个相对关系

    attack
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • 2038:[2009国家集训队]小Z的袜子(hose)

    用户2965768
  • 算法原理系列:木桶排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 挑战程序竞赛系列(59):4.6树上的分治法(2)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447

扫码关注云+社区

领取腾讯云代金券