两个升序整型数组求交集

下面是2020年9月16日面试遇到的一道真实面试题。

题目

求两个升序整型数组的交集。
例如：
数组A：1，2，3，4，5，6，7，8
数组B：2，4，6，10
结果：2，4，6

解题思路

假设数组A长度为m，数组B长度为n。
全部遍历两个数组，可以找到交集，不过时间复杂度为O(m*n)。这种方法没有用到数据升序的条件，这也是提升时间复杂度的关键。
两个数组存在升序，之后遍历的数组元素一定大于已经遍历过的元素，之前不是交集的元素未来也不会出现在交集中。
具体地，两个指针分别指向两个数组，分别顺序遍历，会出现三种情况：
情形1. A[i] == B[j]：此时找到一个交集元素，下次寻找时，i和j继续前进到下一个元素即可。
情形2. A[i] > B[j]：B[j]小，那么j自己要继续向前移动，找到下一个更大的元素，再与A[i]比较。
情形3. A[i] < B[j]：A[i]小，则i自己继续前进，找到下一个更大的元素，再与B[j]比较。

根据上面的思路，代码如下，时间复杂度为线性的O(m+n)：

public int[] intersection(int[] arr1, int[] arr2){
    List<Integer> res = new LinkedList<>();
    //健壮性校验
    if (null == arr1 || arr1.length == 0){
        return arr2;
    }
    if (null == arr2 || arr2.length == 0){
        return arr1;
    }
    //i是数组arr1的下标，j是数组arr2的下标
    int j = 0, i = 0;
    while (j < arr2.length && i < arr1.length){
        if (arr1[i] == arr2[j]){//情形1
            res.add(arr1[i]);
            j++;
            i++;
        } else if (arr1[i] > arr2[j]){//情形2
            j++;
        } else{//情形3
            i++;
        }
    }
    //整理成数组返回交集
    int[] resA = new int[res.size()];
    for (int k = 0; k < res.size(); ++k){
        resA[k] = res.get(k);
    }
    return resA;
}