【LeetCode】多个数组求交集 Java 题解

2022 年 6 月 17 日
本文字数：848 字
阅读完需：约 3 分钟

题目描述

给你一个二维整数数组 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] 的整数，所以返回一个空列表 [] 。
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/intersection-of-multiple-arrays著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是数组处理题目，题目要求求多个数组求交集。题目比较容易理解。在求解的过程中，我们需要记录出现的元素和频次，最常用的数据结构就是 hashmap 了。题目要求返回值是升序。我们需要对 hashmap 中的数据排序。
除了 hashMap, 还有一种数据结构 treeMap, 可以对 key 进行排序，减少我们的排序工作。
以上是 map 相关的解法。再次分析这个题目， num 只有数字，我们也可以直接使用数组来存储元素和元素出现频次。数组是一段连续的内存空间，天然排序，执行效率比较高。实现代码如下，供参考。

通过代码

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