Leetcode 349 两个数组的交集 ( Intersection of Two Arrays *Easy* ) 题解分析

发表于 分类于 ， 阅读次数： 阅读次数： Disqus：

题目介绍

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

 

示例

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的  

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

分析与题解

两个数组的交集，最简单就是两层循环了把两个都存在的找出来，不过还有个要去重的问题，稍微思考下可以使用集合 set 来处理，先把一个数组全丢进去，再对比另外一个，如果出现在第一个集合里就丢进一个新的集合，最后转换成数组，这次我稍微取了个巧，因为看到了提示里的条件，两个数组中的元素都是不大于 1000 的，所以就搞了个 1000 长度的数组，如果在第一个数组出现，就在对应的下标设置成 1，如果在第二个数组也出现了就加 1，

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public int[] intersection(int[] nums1, int[] nums2) {
    // 大小是 1000 的数组，如果没有提示的条件就没法这么做
    // define a array which size is 1000, and can not be done like this without the condition in notice
        int[] inter = new int[1000];
        int[] outer;
        int m = 0;
        for (int j : nums1) {
            //  这里得是设置成 1，因为有可能 nums1 就出现了重复元素，如果直接++会造成结果重复
            // need to be set 1, cause element in nums1 can be duplicated
            inter[j] = 1;
        }
        for (int j : nums2) {
            if (inter[j] > 0) {
                // 这里可以直接+1，因为后面判断只需要判断大于 1
                // just plus 1, cause we can judge with condition that larger than  1
                inter[j] += 1;
            }
        }
        for (int i = 0; i < inter.length; i++) {
            // 统计下元素数量
            // count distinct elements
            if (inter[i] > 1) {
                m++;
            }
        }
        // initial a array of size m
        outer = new int[m];
        m = 0;
        for (int i = 0; i < inter.length; i++) {
            if (inter[i] > 1) {
                // add to outer
                outer[m++] = i;
            }
        }
        return outer;
    }