2248-多个数组求交集

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:23 2023-09-13 16:06:23 Updated    

给你一个二维整数数组 nums ，其中 nums[i] 是由 不同 正整数组成的一个非空数组，按 升序排列
返回一个数组，数组中的每个元素在 nums 所有数组 中都出现过。

示例 1：

**输入：** nums = [[ _ **3**_ ,1,2, _ **4**_ ,5],[1,2, _ **3**_ , _ **4**_ ],[ _ **3**_ , _ **4**_ ,5,6]]
**输出：** [3,4]
**解释：**
nums[0] = [ _ **3**_ ,1,2, _ **4**_ ,5]，nums[1] = [1,2, _ **3**_ , _ **4**_ ]，nums[2] = [ _ **3**_ , _ **4**_ ,5,6]，在 nums 中每个数组中都出现的数字是 3 和 4 ，所以返回 [3,4] 。

示例 2：

**输入：** nums = [[1,2,3],[4,5,6]]
**输出：** []
**解释：**
不存在同时出现在 nums[0] 和 nums[1] 的整数，所以返回一个空列表 [] 。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= sum(nums[i].length) <= 1000
  • 1 <= nums[i][j] <= 1000
  • nums[i] 中的所有值 互不相同

方法一：模拟

思路与算法

我们可以用哈希集合来模拟求解交集的过程。具体地，我们用哈希集合 res 存储第一个数组 nums}[0] 的所有元素，随后，我们遍历二维数组 nums 的剩余元素。遍历元素 nums}[i] 时，我们用另一个哈希集合 tmp 来存储 res 和 nums}[i] 中元素的交集。我们可以通过遍历 nums}[i] 判断每个元素是否在 res 中。最后，我们令 res} = \textit{tmp，即为前 i + 1 个数组的交集。

最终，res 即为所有数组的元素交集。我们用数组记录哈希集合 res 的所有元素，并排序后作为答案返回。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        int n = nums.size();
        unordered_set<int> res(nums[0].begin(), nums[0].end());
        for (int i = 1; i < n; ++i) {
            unordered_set<int> tmp;
            for (int num: nums[i]) {
                if (res.count(num)) {
                    tmp.insert(num);
                }
            }
            res = tmp;
        }
        vector<int> ans(res.begin(), res.end());
        sort(ans.begin(), ans.end());
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        n = len(nums)
        res = set(nums[0])
        for i in range(1, n):
            tmp = set()
            for num in nums[i]:
                if num in res:
                    tmp.add(num)
            res = tmp
        return sorted(res)

复杂度分析

  • 时间复杂度：O(\sum_i n_i + \min(n_i)\log\min(n_i))，其中 n_i 为 nums}[i] 的长度。其中遍历求交集的时间复杂度为 O(\sum_i n_i)，对结果排序的时间复杂度为 O(\min(n_i)\log\min(n_i))。

  • 空间复杂度：O(\max(n_i))，即为辅助哈希集合的空间开销。

方法二：统计每个整数的出现次数

思路与算法

我们用 n 表示二维数组 nums 的长度。由于二维数组 nums 里面的每个数组中的元素互不相同，因此如果一个元素在每个数组中均出现过，则它在 nums 中的出现次数应当等于 n。

因此我们可以用哈希表 freq 维护每个整数的出现次数，随后我们遍历 nums 并维护哈希表 freq。最终，我们遍历 freq 并用 res 数组记录所有出现次数等于 n 的整数，然后返回排序后的 res 数组作为答案。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        int n = nums.size();
        unordered_map<int, int> freq;
        for (const auto& arr: nums) {
            for (int num: arr) {
                ++freq[num];
            }
        }
        vector<int> res;
        for (const auto& [k, v]: freq) {
            if (v == n) {
                res.push_back(k);
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        n = len(nums)
        freq = defaultdict(int)
        for arr in nums:
            for num in arr:
                freq[num] += 1
        res = []
        for k, v in freq.items():
            if v == n:
                res.append(k)
        return sorted(res)

复杂度分析

  • 时间复杂度：O(\sum_i n_i + \min(n_i)\log\min(n_i))，其中 n_i 为 nums}[i] 的长度。即为遍历统计每个整数出现次数，遍历哈希表统计结果以及排序的时间复杂度。

  • 空间复杂度：O(\max_i n_i)，即为辅助哈希表的时间复杂度。

 Comments
On this page
2248-多个数组求交集