【每日算法】力扣350 两个数组的交集 II

发表于

这是我参与11月更文挑战的第25天，活动详情查看：2021最后一次更文挑战。

描述

给定两个数组，编写一个函数来计算它们的交集。

1
2
3
4
5
6
7
8
ini复制代码示例 1：

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

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

说明：

  • 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
  • 我们可以不考虑输出结果的顺序。

做题

这个说明的第一条我没太看懂。

从题目“两个数组的交集”上推测，应该是不需要考虑两个数组的顺序。

我一开始还以为，要考虑两个数组的顺序，像 试例 2 的 [4,9] 就有顺序，那样就比较难做了，唯一的做法可能就是两层遍历循环了。

因为不需要考虑结果的顺序，所以我们可以考虑使用 map 来存储每个数出现的个数，然后取相同的次数最少的数作为结果返回。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
java复制代码public int[] intersect(int[] nums1, int[] nums2) {
    Map<Integer,Integer> map1=new HashMap<>();
    Map<Integer,Integer> map2=new HashMap<>();

    for (int i = 0; i < nums1.length; i++) {
        int num = nums1[i];
        Integer integer = map1.get(num);
        if (integer == null){
            integer = 1;
            map1.put(num,integer);
            continue;
        }
        integer +=1;
        map1.put(num,integer);
    }

    for (int i = 0; i < nums2.length; i++) {
        int num = nums2[i];
        Integer integer = map2.get(num);
        if (integer == null){
            integer = 1;
            map2.put(num,integer);
            continue;
        }
        integer +=1;
        map2.put(num,integer);
    }

    List<Integer> list = new ArrayList<>();
    Set<Integer> integers = map1.keySet();
    Iterator<Integer> iterator = integers.iterator();
    while (iterator.hasNext()){
        Integer next = iterator.next();
        Integer integer2 = map2.get(next);
        if (integer2==null){
            continue;
        }
        Integer integer1 = map1.get(next);
        integer1=integer2>integer1?integer1:integer2;
        while (integer1-->0){
            list.add(next);
        }
    }
    int[] result = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        result[i]=list.get(i);
    }

    return result;
}

image.png

跑是跑通了。

但是效率好低，代码也很长。

这部分代码优化一下，把它和第二循环结合到一起，降低时间复杂度。

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
ini复制代码public int[] intersect1(int[] nums1, int[] nums2) {
    Map<Integer,Integer> map1=new HashMap<>();
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < nums1.length; i++) {
        int num = nums1[i];
        Integer integer = map1.get(num);
        if (integer == null){
            integer = 1;
            map1.put(num,integer);
            continue;
        }
        map1.put(num,++integer);
    }

    for (int i = 0; i < nums2.length; i++) {
        int num = nums2[i];
        Integer integer1 = map1.get(num);
        if (integer1 == null){
            //当 integer1 等于 null 时，就不需要再做后面的操作了
            continue;
        }
        if ( integer1!=0){
            list.add(num);
            map1.put(num,--integer1);
        }

    }
    int[] result = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        result[i]=list.get(i);
    }

    return result;
}

不优化不知道，一优化就减少了二十多行代码，还把 map2 优化掉了。

image.png

不过这个运行结果怎么内存占用还变高了？

今天就到这里了。

这里是程序员徐小白，【每日算法】是我新开的一个专栏，在这里主要记录我学习算法的日常，也希望我能够坚持每日学习算法，不知道这样的文章风格您是否喜欢，不要吝啬您免费的赞，您的点赞、收藏以及评论都是我下班后坚持更文的动力。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%