力扣2248:多个数组求交集(Java多种方法)

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

一、题目描述



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


二、思路讲解



2.1 方法一:统计数字出现次数


因为nums[i]中所有的值互不相同,所以我们可以统计数组在nums中出现过的次数,如果出现次数和nums的长度相同,说明是交集中的值


class Solution {
    public List<Integer> intersection(int[][] nums) {
        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++) {
            for(int j=0; j<nums[i].length; j++) {
                map.put(nums[i][j], map.getOrDefault(nums[i][j], 0) + 1);
                if(map.get(nums[i][j]) == nums.length) {
                    list.add(nums[i][j]);
                }
            }
        }
        Collections.sort(list);
        return list;
    }
}


2.2 方法二:模拟

     

模拟集合求交集的方式,定义哈希集合res,并将第一个集合中的值放入res中,若后面的数组中的数在res中,则放入temp集合中,然后res = temp。res就是前i个数组的交集。


class Solution {
    public List<Integer> intersection(int[][] nums) {
        //存储交集
        Set<Integer> res = new HashSet<>(); 
        //将第一个数组的值赋给set
        for(int i=0; i<nums[0].length; i++) {
            res.add(nums[0][i]);
        }
        //求前i个数组的交集
        for(int i=1; i<nums.length; i++) {
            Set<Integer> temp = new HashSet<>();
            for(int j=0; j<nums[i].length; j++) {
                if(res.contains(nums[i][j])) {
                    temp.add(nums[i][j]);
                }
            }
            res = temp;
        }
        List<Integer> list = new ArrayList(res);
        Collections.sort(list);
        return list;
    }
}


相关文章
|
2月前
|
存储 缓存 算法
Java 数组
【10月更文挑战第19天】Java 数组是一种非常实用的数据结构,它为我们提供了一种简单而有效的方式来存储和管理数据。通过合理地使用数组,我们能够提高程序的运行效率和代码的可读性。更加深入地了解和掌握 Java 数组的特性和应用,为我们的编程之旅增添更多的精彩。
33 4
|
2月前
|
存储 缓存 算法
提高 Java 数组性能的方法
【10月更文挑战第19天】深入探讨了提高 Java 数组性能的多种方法。通过合理运用这些策略,我们可以在处理数组时获得更好的性能表现,提升程序的运行效率。
37 2
|
2月前
|
存储 Java
Java“(array) <X> Not Initialized” (数组未初始化)错误解决
在Java中,遇到“(array) &lt;X&gt; Not Initialized”(数组未初始化)错误时,表示数组变量已被声明但尚未初始化。解决方法是在使用数组之前,通过指定数组的大小和类型来初始化数组,例如:`int[] arr = new int[5];` 或 `String[] strArr = new String[10];`。
91 2
|
2月前
|
存储 Java
什么是带有示例的 Java 中的交错数组?
什么是带有示例的 Java 中的交错数组?
53 9
|
2月前
|
Java
Java数组动态扩容和动态缩减
Java数组动态扩容和动态缩减
25 3
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
21 4
|
2月前
|
存储 Java 程序员
【一步一步了解Java系列】:何为数组,何为引用类型
【一步一步了解Java系列】:何为数组,何为引用类型
31 1
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
21 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
|
存储 算法 Java
带你学习java的数组军队列
带你学习java的数组军队列
36 0
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
69 0