2248. 多个数组求交集

问题描述

给你一个二维整数数组 nums，其中 nums[i] 是一个非空数组，包含 nums[i] 中的所有整数。返回一个按升序排列且在所有数组中都存在的整数列表。

示例：

输入: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
输出: [3,4]
解释: 3和4在所有数组中都存在

输入: nums = [[1,2,3],[4,5,6]]
输出: []
解释: 没有在所有数组中都存在的数字

算法思路

方法一：哈希表计数（推荐解法）

1. 使用 HashMap 统计每个数字在多少个数组中出现
2. 遍历所有数组，对每个数组中的唯一元素进行计数（避免同一数组内重复计数）
3. 最终统计结果等于数组总数的数字，即为交集元素
4. 按升序返回结果

优点：时间O(N)，空间O(U)，N为总元素数，U为唯一元素数

方法二：逐个求交集

1. 从第一个数组开始，作为初始交集
2. 依次与后续每个数组求交集
3. 使用集合操作高效实现
4. 最后排序返回

优点：逻辑清晰，易于理解

方法三：位运算（当数值范围小时）

1. 如果数值范围较小（如0-1000），可用位向量
2. 为每个数组创建位向量
3. 按位与所有位向量
4. 为1的位对应交集元素

优点：空间效率极高，当范围小时最优

代码实现

方法一：哈希表计数（推荐解法）

import java.util.*;

class Solution {
    /**
     * 找出多个数组的交集（哈希表计数法）
     * 
     * 核心思想：频次统计
     * 1. 统计每个数字在多少个数组中出现
     * 2. 对每个数组去重后计数，避免同一数组内重复计数
     * 3. 出现频次等于数组总数的数字即为交集元素
     * 
     * @param nums 二维整数数组，包含多个非空数组
     * @return 按升序排列的交集元素列表
     */
    public List<Integer> intersection(int[][] nums) {
        int arrayCount = nums.length;  // 数组的总数量
        
        // HashMap统计每个数字在多少个数组中出现
        // key: 数字, value: 出现在多少个数组中
        Map<Integer, Integer> countMap = new HashMap<>();
        
        // 遍历每个数组
        for (int[] array : nums) {
            // 使用Set对当前数组去重
            // 避免同一数组内的重复元素被多次计数
            Set<Integer> uniqueInCurrentArray = new HashSet<>();
            for (int num : array) {
                uniqueInCurrentArray.add(num);
            }
            
            // 对当前数组中的唯一元素进行计数
            for (int num : uniqueInCurrentArray) {
                countMap.put(num, countMap.getOrDefault(num, 0) + 1);
            }
        }
        
        // 收集在所有数组中都出现的元素（计数等于数组总数）
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() == arrayCount) {
                result.add(entry.getKey());
            }
        }
        
        // 按升序排列
        Collections.sort(result);
        
        return result;
    }
}

方法二：逐个求交集

import java.util.*;

class Solution {
    /**
     * 找出多个数组的交集（逐个求交集法）
     * 
     * 核心思想：迭代求交集
     * 1. 将第一个数组转为集合，作为初始交集
     * 2. 依次与后续每个数组求交集
     * 3. 使用集合的retainAll操作高效实现
     * 
     * @param nums 二维整数数组
     * @return 按升序排列的交集元素列表
     */
    public List<Integer> intersection(int[][] nums) {
        // 将第一个数组转为有序集合
        Set<Integer> intersectionSet = new TreeSet<>();
        for (int num : nums[0]) {
            intersectionSet.add(num);
        }
        
        // 依次与后续每个数组求交集
        for (int i = 1; i < nums.length; i++) {
            // 将当前数组转为集合
            Set<Integer> currentSet = new HashSet<>();
            for (int num : nums[i]) {
                currentSet.add(num);
            }
            
            // 求交集：保留intersectionSet中也存在于currentSet的元素
            intersectionSet.retainAll(currentSet);
            
            // 优化：如果交集为空，可提前终止
            if (intersectionSet.isEmpty()) {
                break;
            }
        }
        
        // 转换为列表（TreeSet已有序）
        return new ArrayList<>(intersectionSet);
    }
}

方法三：优化的哈希表计数

import java.util.*;

class Solution {
    /**
     * 优化版本：使用TreeSet直接维护有序结果
     * 
     * 核心思想：在收集结果时直接排序
     * 使用TreeSet替代ArrayList + Collections.sort
     * 
     * @param nums 二维整数数组
     * @return 按升序排列的交集元素列表
     */
    public List<Integer> intersection(int[][] nums) {
        int arrayCount = nums.length;
        Map<Integer, Integer> countMap = new HashMap<>();
        
        // 统计每个数字在多少个数组中出现
        for (int[] array : nums) {
            Set<Integer> uniqueInArray = new HashSet<>();
            for (int num : array) {
                uniqueInArray.add(num);
            }
            
            for (int num : uniqueInArray) {
                countMap.put(num, countMap.getOrDefault(num, 0) + 1);
            }
        }
        
        // 使用TreeSet直接得到有序结果
        TreeSet<Integer> result = new TreeSet<>();
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() == arrayCount) {
                result.add(entry.getKey());
            }
        }
        
        return new ArrayList<>(result);
    }
}

算法分析

• 时间复杂度：

  • 方法一（哈希表）：O(N + U log U)
    • N：所有数组的总元素数
    • U：唯一元素总数
    • 排序O(U log U)可能成为主导
  • 方法二（逐个交集）：O(N + U log U)
    • 每次retainAll操作O(min)
    • TreeSet维护有序性
  • 方法三（优化）：同方法一

• 空间复杂度：

  • 方法一：O(U)
    • countMap存储所有唯一元素
    • 结果集O(U)
  • 方法二：O(U)
    • 交集集合和临时集合
  • 方法三：O(U)，同方法一

• 方法对比：

  方法	时间复杂度	空间复杂度	优点	缺点
  哈希表计数	O(N+U log U)	O(U)	逻辑清晰，易于理解	需要额外排序
  逐个交集	O(N+U log U)	O(U)	迭代思想直观	多次集合操作开销
  优化版本	O(N+U log U)	O(U)	代码简洁	TreeSet常数因子较大

算法过程

输入：nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]

方法一：哈希表计数过程

arrayCount = 3

遍历数组0 [3,1,2,4,5]:
  unique = {1,2,3,4,5}
  countMap: {1:1, 2:1, 3:1, 4:1, 5:1}

遍历数组1 [1,2,3,4]:
  unique = {1,2,3,4}
  countMap: {1:2, 2:2, 3:2, 4:2, 5:1}

遍历数组2 [3,4,5,6]:
  unique = {3,4,5,6}
  countMap: {1:2, 2:2, 3:3, 4:3, 5:2, 6:1}

收集计数=3的元素: [3,4]
排序: [3,4]

方法二：逐个求交集过程

初始交集: {1,2,3,4,5} (来自nums[0])

与nums[1]=[1,2,3,4]求交集:
  intersectionSet.retainAll({1,2,3,4})
  结果: {1,2,3,4}

与nums[2]=[3,4,5,6]求交集:
  intersectionSet.retainAll({3,4,5,6})
  结果: {3,4}

返回: [3,4] (TreeSet已有序)

测试用例

public static void main(String[] args) {
    Solution solution = new Solution();
    
    // 测试用例1：示例1
    int[][] nums1 = {{3,1,2,4,5},{1,2,3,4},{3,4,5,6}};
    System.out.println("Test 1: " + solution.intersection(nums1)); // [3,4]
    
    // 测试用例2：示例2
    int[][] nums2 = {{1,2,3},{4,5,6}};
    System.out.println("Test 2: " + solution.intersection(nums2)); // []
    
    // 测试用例3：所有数组相同
    int[][] nums3 = {{1,2},{1,2},{1,2}};
    System.out.println("Test 3: " + solution.intersection(nums3)); // [1,2]
    
    // 测试用例4：只有一个数组
    int[][] nums4 = {{1,3,2}};
    System.out.println("Test 4: " + solution.intersection(nums4)); // [1,2,3]
    
    // 测试用例5：空结果（有部分交集）
    int[][] nums5 = {{1,2},{2,3},{3,1}};
    System.out.println("Test 5: " + solution.intersection(nums5)); // []
    
    // 测试用例6：完全相同的数字
    int[][] nums6 = {{1,1,1},{1,1},{1}};
    System.out.println("Test 6: " + solution.intersection(nums6)); // [1]
    
    // 测试用例7：大范围数字
    int[][] nums7 = {{10,20,30},{20,30,40},{30,40,50}};
    System.out.println("Test 7: " + solution.intersection(nums7)); // [30]
}

关键点

1. 去重的重要性：

   • 必须对每个数组内部去重
   • 避免同一数组内的重复元素被多次计数

2. 计数逻辑：

   • 统计的是"在多少个数组中出现"，不是总出现次数
   • 只有出现在所有数组中的元素才计入交集

3. 排序要求：

   • 题目要求升序排列
   • 可在最后排序，或使用有序数据结构

4. 边界情况：

   • 单个数组：返回去重排序后的所有元素
   • 无交集：返回空列表
   • 空数组：题目保证非空

5. 性能优化：

   • 逐个交集法可在交集为空时提前终止
   • 选择较小的数组作为初始交集可提高效率

常见问题

1. 为什么需要对每个数组去重？

   • 因为要统计"在多少个数组中出现"
   • 同一数组内的重复元素只应计为1次
   • 否则会错误地增加计数

2. retainAll方法的原理？

   • set1.retainAll(set2)：保留set1中也存在于set2的元素
   • 时间复杂度O(min(set1.size(), set2.size()))
   • 是求集合交集的高效方式

3. 如果数组数量很大怎么办？

   • 算法复杂度与数组数量线性相关
   • 可考虑并行处理，但LeetCode通常不需要

4. 能否用位运算？

   • 如果数字范围小（如0-1000），可以用位向量
   • 创建1001位的向量，按位与所有数组的位向量
   • 空间O(1)，时间O(N)

5. 如何处理负数？

   • 算法支持负数
   • HashMap和Set能正确处理负数键
   • 排序时负数会正确排在前面