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("存在");
}

上一篇:数据结构算法 | 单调栈


下一篇:javaScript力扣刷题——简单数组(三)