2248. 多个数组求交集

题目

给你一个二维整数数组 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 <= <= 1000
nums[i] 中的所有值 互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-multiple-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

因为最大的数不超过1000，因此可以判断1到1000之间的数是否存在于每个数组中，比赛时用python纯暴力，写的快一点。见代码二

更好的办法是使用一个数组或者哈希表统计出现的数的次数，最后出现n次的就是要找的，其中n为nums的长度。见代码一

代码

Java 代码一

class Solution {
    public List<Integer> intersection(int[][] nums) {
        int[] cnt = new int[1001];
        for (int[] arr : nums) {
            for (int value : arr) {
                cnt[value]++;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < 1001; i++) {
            if (cnt[i] == nums.length) {
                ans.add(i);
            }
        }
        return ans;
    }
}

py3 暴力 代码二

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        ans = []
        for i in range(1001):
            flag = True
            for list in nums:
                if i not in list:
                    flag = False
                    break
            if flag:
                ans.append(i)
        return ans