Java教程

Java 求解两个数组的交集

本文主要是介绍Java 求解两个数组的交集,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

    • 一、题目
    • 二、哈希思路
    • 三、代码
    • 四、总结

一、题目

给定两个数组,编写一个函数来计算它们的交集。
在这里插入图片描述

二、哈希思路

暴力破解的思路就是遍历 nums1 的过程中,遍历 nums2 ,时间复杂度 O ( n 2 ) O(n^2) O(n2)

题目已经说明,输出结果中每个元素唯一,可以把 nums1 的元素映射到哈希数组上,然后遍历 nums2时,判断是否出现过就可以

对于数组的使用,需要限制数值的大小,而且如果哈希值比较少,特别分散,跨度大,使用数组就容易造成空间的浪费

所以,本题采用 set 集合充当哈希表,也符合题目要求的去重效果

三、代码

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
        int[] resArr = new int[resSet.size()];
        int index = 0;
        //将结果几何转为数组
        for (int i : resSet) {
            resArr[index++] = i;
        }
        return resArr;
    }
}

四、总结

对于数组的使用,需要限制数值的大小,而且如果哈希值比较少,特别分散,跨度大,使用数组就容易造成空间的浪费

所以,对于没有说明数值大小,或者有去重需求的题目采用 set 集合充当哈希表

//set集合添加元素
set.add(i);
//获取set集合大小
set.size();
//判断set集合是否存在某元素
if(set.contains(i)){
	System.out.println("存在");
}

这篇关于Java 求解两个数组的交集的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!