LeetCode 349. Intersection of Two Arrays [Easy]

题目来源：https://leetcode.com/problems/intersection-of-two-arrays/

题目难度：Easy

解答1[Java]

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set1 = new HashSet();
        HashSet<Integer> set2 = new HashSet();
        HashSet resultSet = new HashSet();
        int[] result = new int[nums1.length];
        int resultIndex = 0;

        for(int num: nums1){
            set1.add(num);
        }

        for(int num:nums2){
            set2.add(num);
        }

        for (Integer num :set2){
            if(set1.contains(num)){
                result[resultIndex++] = num;
            }
        }

        return Arrays.copyOf(result, resultIndex);

    }
}

复杂度分析

没错，hashSet的contains方法是调用map.containsKey(O)方法的，containsKey(o)是根据hash函数去做散列的，所以与元素的多少无关，无论是多少元素containsKey(o)的时间复杂度基本上O(1)。

HashSet细节 - 小菜园博客

解答2[Java]：

import java.util.Arrays;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : nums1) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        boolean[] exist = new boolean[max - min + 1];
        for (int num : nums1) exist[num - min] = true;
        int[] result = new int[nums2.length];
        int index = 0;
        for (int num : nums2) {
            if (num <= max && num >= min && exist[num - min]) {
                result[index++] = num;
                exist[num - min] = false; //remove from exist array to avoid duplicate
            }
        }
        return Arrays.copyOf(result, index);
    }
}

思路

很巧妙的一个算法，先把一个数组的最大值和最小值圈起来。

复杂度分析

空间复杂度：

result 数组和 exist 数组为 $O(m)$ 或者 $O(h)$。m 和 h 是两个数组的长度。

时间复杂度：$O(n)$。