当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.349.Intersection of Two Arrays 两数组的交集

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


上一篇 LeetCode.541.Reverse String II 反转字符串 II

下一篇 LeetCode.389.Find the Difference 找出两个数组的不同

阅读
评论
539
阅读预计2分钟
创建日期 2018-01-25
修改日期 2018-01-26
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论