递归查找两个未排序整数数组公共元素的代码问题排查

问题描述 #

给定两个未排序整数数组，需输出它们的公共元素。示例数组：
int[] list1 = {4,5,6,7,8}
int[] list2 = {2,3,4,8,10,16}
当前代码仅输出4，正确输出应为4 8，原代码如下：

public static void commonElements(int[] a,int[] b){
helper(a,b,0,0);
    }
    public static void helper(int[] a, int[] b,int i,int j){
        if(i == a.length || j ==b.length){
            return;
        }else if(a[i] == b[j]) {
            System.out.println(a[i]);
            helper(a,b,++i,0);
        } else {
            helper(a, b, i, j+1);
        }
    }

错误原因 #

1. 终止逻辑缺陷：当遍历完list2（j == b.length）时直接返回，没有继续检查list1的下一个元素。比如找到4后，i变为1（对应元素5），遍历完list2无匹配就直接终止，根本没机会检查list1中的8。
2. 输出格式问题：使用println会让每个元素单独换行，不符合4 8的连续输出要求。

修复后的递归代码 #

public static void commonElements(int[] a,int[] b){
    helper(a,b,0,0);
}

public static void helper(int[] a, int[] b,int i,int j){
    // 所有元素检查完毕，终止递归
    if(i == a.length){
        return;
    }
    // 当前list1元素遍历完list2无匹配，检查下一个list1元素
    if(j == b.length){
        helper(a,b,i+1,0);
        return;
    }
    if(a[i] == b[j]) {
        System.out.print(a[i] + " ");
        // 找到匹配，继续检查下一个list1元素
        helper(a,b,i+1,0);
    } else {
        // 继续遍历list2的下一个元素
        helper(a, b, i, j+1);
    }
}

更高效的非递归方案（推荐） #

递归方法时间复杂度为O(n*m)，当数组规模较大时效率较低。可以用HashSet将时间复杂度优化到O(n+m)：

import java.util.HashSet;

public static void commonElements(int[] a, int[] b) {
    HashSet<Integer> elementSet = new HashSet<>();
    // 将list1元素存入集合
    for (int num : a) {
        elementSet.add(num);
    }
    // 遍历list2，查找公共元素
    for (int num : b) {
        if (elementSet.contains(num)) {
            System.out.print(num + " ");
            elementSet.remove(num); // 避免重复输出（若数组含重复元素）
        }
    }
}

内容的提问来源于stack exchange，提问作者amr khaled