Leetcode 1213:三个有序数组的交集(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1213:三个有序数组的交集(超详细的解法!!!)

in leetcode with 0 comment

给出三个均为 严格递增排列 的整数数组 arr1arr2arr3

返回一个由 在这三个数组中 同时出现 的整数所构成的有序数组。

示例:

输入: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
输出: [1,5]
解释: 只有 1 和 5 同时在这三个数组中出现.

提示:

  1. 1 <= arr1.length, arr2.length, arr3.length <= 1000
  2. 1 <= arr1[i], arr2[i], arr3[i] <= 2000

解题思路

如果使用python的话,一行就解决了。三个数组集合求交集,然后排序,即为最后的结果。

class Solution:
    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        return sorted(set(arr1) & set(arr2) & set(arr3))

使用cpp的话,也可以非常简洁。

class Solution
{
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) 
    {
        vector<int> arr12;
        set_intersection(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), back_inserter(arr12));
        vector<int> res;
        set_intersection(arr12.begin(), arr12.end(), arr3.begin(), arr3.end(), back_inserter(res));
        return res;
    }
};

当然,如果不用高级语法的话,也可以通过map来处理(如果语言没有map,使用数组即可)。分别遍历arr1arr2arr3,将其中的元素添加到map中,然后遍历map判断有没有元素出现三次的,如果有那个元素即为三者的相交元素。

class Solution
{
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) 
    {
        map<int, int> d;
        for (auto x : arr1) d[x]++;
        for (auto x : arr2) d[x]++;
        for (auto x : arr3) d[x]++;
        vector<int> res;
        for (auto& it : d)
        {
            if (it.second == 3) res.push_back(it.first);
        }
        return res;
    }
};

当然你可以将上面代码继续优化一下。遍历数组arr3的时候,只要判断相应元素是不是出现过两次即可。

class Solution
{
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) 
    {
        map<int, int> d;
        for (auto x : arr1) d[x]++;
        for (auto x : arr2) d[x]++;
        
        vector<int> res;
        for (auto x : arr3) {
            if (d[x] == 2) res.push_back(x);
        }
        return res;
    }
};

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses