Easy

题目描述

给你一个二维整数数组 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] 中都出现的整数只有 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] 的所有值互不相同

解题思路

解题思路

这道题要求找到在所有数组中都出现的整数，是一个典型的求交集问题。我们可以用以下几种方法解决：

方法一：计数法（推荐） 使用哈希表记录每个数字在多少个数组中出现过。由于题目保证每个数组内的元素都不重复，所以如果一个数字在所有数组中都出现，那么它的出现次数就等于数组的总数量。

方法二：集合交集法 将第一个数组转换为集合，然后依次与后续数组求交集。这种方法在数组较多时效率会降低。

方法三：位运算法 由于数字范围限制在1000以内，可以用位运算来标记每个数字在哪些数组中出现过。

计数法是最直观和高效的解法，时间复杂度为O(sum)，其中sum是所有数组元素的总和，空间复杂度为O(k)，其中k是不重复数字的个数。

代码实现

class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        unordered_map<int, int> count;
        int n = nums.size();
        
        // 统计每个数字出现在多少个数组中
        for (auto& arr : nums) {
            for (int num : arr) {
                count[num]++;
            }
        }
        
        vector<int> result;
        // 找出在所有数组中都出现的数字
        for (auto& p : count) {
            if (p.second == n) {
                result.push_back(p.first);
            }
        }
        
        sort(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        from collections import Counter
        
        count = Counter()
        n = len(nums)
        
        # 统计每个数字出现在多少个数组中
        for arr in nums:
            for num in arr:
                count[num] += 1
        
        # 找出在所有数组中都出现的数字并排序
        result = [num for num, freq in count.items() if freq == n]
        return sorted(result)

public class Solution {
    public IList<int> Intersection(int[][] nums) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        int n = nums.Length;
        
        // 统计每个数字出现在多少个数组中
        foreach (int[] arr in nums) {
            foreach (int num in arr) {
                if (count.ContainsKey(num)) {
                    count[num]++;
                } else {
                    count[num] = 1;
                }
            }
        }
        
        List<int> result = new List<int>();
        // 找出在所有数组中都出现的数字
        foreach (var pair in count) {
            if (pair.Value == n) {
                result.Add(pair.Key);
            }
        }
        
        result.Sort();
        return result;
    }
}

var intersection = function(nums) {
    let count = {};
    
    for (let arr of nums) {
        for (let num of arr) {
            count[num] = (count[num] || 0) + 1;
        }
    }
    
    let result = [];
    for (let num in count) {
        if (count[num] === nums.length) {
            result.push(parseInt(num));
        }
    }
    
    return result.sort((a, b) => a - b);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(sum + k log k)
空间复杂度O(k)

其中 sum 是所有数组元素的总和，k 是不重复数字的个数。时间复杂度中 sum 来自统计过程，k log k 来自最后的排序。

相关题目