LeetCode.349.Intersection of Two Arrays 两数组的交集

题目描述

349 Intersection of Two Arrays
https://leetcode-cn.com/problems/intersection-of-two-arrays/
https://leetcode.com/problems/intersection-of-two-arrays/description/

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
Each element in the result must be unique.
The result can be in any order.

---

解题过程

类似
LeetCode.350.Intersection of Two Arrays II 两数组的交集2

求两数组元素的交集，并且还不能重复，想到的就是利用集合或者哈希表来做。
用哈希表来写，很简单，但我提交了三次才AC，因为从map中取数据map.get(i)后没有判空就直接比较，导致出现空指针异常

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i : nums1)
            map.put(i,1);
        List<Integer> list = new ArrayList<Integer>();
        for(int i : nums2)
            if(map.get(i) != null && map.get(i) == 1){
                list.add(i);
                map.put(i, 2);
            }
        int[] resultInt = list.stream().mapToInt(Integer::intValue).toArray();
        return resultInt;
    }
}

通过后发现效率很低，只打败了3%的代码。

然后看Discuss，用集合实现的确很简单也很清晰：

public int[] intersection(int[] nums1, int[] nums2) {
    HashSet<Integer> set = new HashSet<Integer>();
    ArrayList<Integer> res = new ArrayList<Integer>();
    //Add all elements to set from array 1
    for(int i =0; i< nums1.length; i++) set.add(nums1[i]);
    for(int j = 0; j < nums2.length; j++) {
      // If present in array 2 then add to res and remove from set
      if(set.contains(nums2[j])) {
            res.add(nums2[j]);
            set.remove(nums2[j]);
        }
    }
    // Convert ArrayList to array
    int[] arr = new int[res.size()];
    for (int i= 0; i < res.size(); i++) arr[i] = res.get(i);
    return arr;
}

还看到一个排序后用双指针遍历的，思路不错：

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                set.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] result = new int[set.size()];
        int k = 0;
        for (Integer num : set) {
            result[k++] = num;
        }
        return result;
    }
}

还有人给出了用Java 8的流实现的两行代码版：

Set<Integer> set = Arrays.stream(nums2).boxed().collect(Collectors.toSet());
return Arrays.stream(nums1).distinct().filter(e-> set.contains(e)).toArray();

---

GitHub代码

algorithms/leetcode/leetcode/_349_IntersectionOfTwoArrays.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_349_IntersectionOfTwoArrays.java

---