X

LEETCODE 1213. Intersection of Three Sorted Arrays 解题思路分析

题目大意:

三个有序数组的交集

给出三个均为 严格递增排列 的整数数组 arr1,arr2 和 arr3。

返回一个由 仅 在这三个数组中 同时出现 的整数所构成的有序数组。

示例1:

输入: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
输出: [1,5]
解释: 只有 1 和 5 同时在这三个数组中出现。

提示:

  • 1 <= arr1.length, arr2.length, arr3.length <= 1000
  • 1 <= arr1[i], arr2[i], arr3[i] <= 2000

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1213

解题思路分析:

这道题很简单,我们可以定义三个index,分别代表三个数组的下标,我们从下标0开始遍历三个数组的每个数字。如果当前下标的三个数字相同,则将其加入返回结果集,同时三个下标分别加一。如果3个数不同时,找到一个最大值,用每个数组的当前数去和最大值比较,如果小于最大值,则此数组下标加一。直到循环结束。循环结束条件是当一个数组下标达到末尾。

实现代码:

public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
    int i1=0,i2=0,i3=0; // 定义3个数组下标,默认都是0
    // 返回结果
    List<Integer> res = new ArrayList<>();
    // 当3个数组下标都没有越界时,循环
    while(i1<arr1.length&&i2<arr2.length&&i3<arr3.length){
        // 得到当前3个数组的数值
        int n1=arr1[i1],n2=arr2[i2],n3=arr3[i3];
        // 如果3个数相同,加入返回结果
        if(n1==n2&&n1==n3){
            res.add(n1);
            // 3个下标分别加1
            i1++;
            i2++;
            i3++;
            continue;
        }
        // 如果3个数不同,找到一个最大值
        int max = Math.max(n1,Math.max(n2,n3));
        // 数组1当前值小于最大值,数组1下标加1
        if(n1<max)i1++;
        // 数组2当前值小于最大值,数组2下标加1
        if(n2<max)i2++;
        // 数组3当前值小于最大值,数组3下标加1
        if(n3<max)i3++;
    }
    return res;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Intersection of Three Sorted Arrays.

Memory Usage: 39.2 MB, less than 100.00% of Java online submissions for Intersection of Three Sorted Arrays.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1213-intersection-of-three-sorted-arrays-解题思路分析/
Categories: leetcode
kwantong: