Dimple在左耳听风ARTS打卡（二十三）

程序员小跃

发布于 2019-12-27 15:03:40

2850

发布于 2019-12-27 15:03:40

文章被收录于专栏：程序员小跃程序员小跃

所谓ARTS：每周至少做一个LeetCode的算法题；阅读并点评至少一篇英文技术文章；学习至少一个技术技巧；分享一篇有观点和思考的技术文章。（也就是Algorithm、Review、Tip、Share 简称ARTS）这是第二十三期打卡。

Algorithm LeetCode算法

两个数组的交集 (https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/)

题目描述：给定了两个数组，编写一个函数来计算它们的交集。

示例1：

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

输出：[2,2]

示例2：

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

输出：[4,9]

说明：

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

用哈希表进行题解

还记得刚开始刷算法题的时候，也做过查找的题目，但是刚开始都是通过循环来暴力查找。直到我看到很多更优秀的题解，才发现还可以通过哈希来做性能优化。

所以，拿到这题的第一个感觉就是，是否能通过哈希来解决呢，事实证明是可以的。

首先，我们用HashMap记录第一个数组中的元素，把它存入key，出现的次数存入value，毕竟出现次数可能不止一次。
第二，去遍历第二个数组，如果找到对应元素，添加这个元素到列表
第三，在第二步，找到对应的元素，就把value减1，如果value等于1，需要删除这个key，说明数组1中此元素已经遍历结束，不会再有交集

具体代码如下：

public static int[] intersect(int[] nums1,int[] nums2) {
    // 先把数组一的内容添加到map
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums1.length; i++) {
        if (map.containsKey(nums1[i])) {
            map.put(nums1[i], map.get(nums1[i]) + 1);
        } else {
            map.put(nums1[i], 1);
        }
    }

    // 遍历数组二，找出相同的数据
    List<Integer> info = new ArrayList<>();
    for (int i = 0; i < nums2.length; i++) {
        if (map.containsKey(nums2[i])) {
            info.add(nums2[i]);
            if (map.get(nums2[i]) > 1) {
                map.put(nums2[i], map.get(nums2[i]) -1);
            } else {
                map.remove(nums2[i]);
            }

        }
    }

    // 利用stream，方便转换
    int[] arr2 = info.stream().mapToInt(Integer::valueOf).toArray();    
    return arr2;
}

在这里，小编把List转换成int[]用了stream，关于stream的一些方式，可能有些读者还不大熟悉，小编在后面Tip 一个技术技巧里做了一部分记录。

Review 阅读并点评至少一篇英文文章

Android Architecture Components (https://developer.android.com/topic/libraries/architecture)

前几天和一位球友聊天，聊到了Android上的AAC框架，因为自己没有去用过这个框架，所以就去官网找资料。

以前学习Android的时候，就是去官网找的资料，现在还是这样，Google本身对这些自己开源的东西很上心，而且还算是比较详细了。

AAC框架，在这份文档里写的还是蛮好的，还有不过需要仔细观看，我也就是走马观花有个大概的了解罢了。如果你也感兴趣，欢迎一起来交流噢。

Tip 一个技术技巧

说来也巧，最近在学习《Java性能调优实战》的课程，刚好有关于Stream一节的讲解，用Stream来处理遍历，在一定情况下能提升性能，感兴趣的同学，可以去看看该专栏的第6课。

什么是Stream

在 Java8 之前，我们通常是通过 for 循环或者 Iterator 迭代来重新排序合并数据，又或者通过重新定义Collections.sorts的Comparator方法来实现，这两种方式对于大数据量系统来说，效果并不是很理想。

Java 8中添加了一个新的接口类Stream，他和我们之前接触的字节流概念不太一样，Java 8集合中的Stream相当于高级别版的Iterator，他可以通过Lambda表达式对集合进行各种非常便利、高效的聚合操作（Aggregate Operation），或者大批量数据操作（Bulk Data Operation）。

我们在应用层就可以高效地实现类似数据库SQL的聚合操作，而在数据操作方面，Stream不仅可以通过串行的方式实现数据操作，还可以通过并行的方式处理大批量数据，提高数据的处理效率。

Stream转换

那么回到我们算法题里使用的奖List转换成int[]，就是通过stream的转换得来的结果。

// List<Integer> 转 int[]
int[] arr1 = list1.stream().mapToInt(Integer::valueOf).toArray();
// 想要转换成int[]类型，就得先转成IntStream。
// 这里就通过mapToInt()把Stream<Integer>调用Integer::valueOf来转成IntStream
// 而IntStream中默认toArray()转成int[]。

// Integer[] 转 int[]
int[] arr2 = Arrays.stream(integers1).mapToInt(Integer::valueOf).toArray();
// 思路同上。先将Integer[]转成Stream<Integer>，再转成IntStream。

关于Stream还有很多需要学习的地方，这一小部分还只是皮毛，在后续的学习中，小编再好好整理一番。