如何用递归合并两个有序int数组？当前仅合并部分元素

你的代码存在几个关键问题，导致只能合并前5个元素，以下是问题分析和修正方案：

问题点分析 #

1. 终止条件逻辑错误：你用a[i] > a.length判断数组是否遍历完成，这是拿数组元素值和数组长度做比较，完全不符合逻辑。正确判断应该是索引是否超出数组范围，即i >= a.length或j >= b.length。
2. 未处理单个数组遍历完成的情况：当其中一个数组已经遍历完所有元素，需要把另一个数组剩余的元素全部追加到结果数组中，原代码直接返回，导致剩余元素无法加入。
3. 遗漏元素相等的情况：原代码只处理了a[i] < b[j]和a[i] > b[j]，当两个元素相等时没有任何操作，递归无法继续推进。
4. main方法冗余调用：循环里重复调用combineArray会重新触发合并逻辑，虽然这里因为复用同一个c数组影响不大，但完全没必要，直接用合并后的结果数组遍历即可。

修正后的代码 #

public class findMe {
    public int[] combineArray(int[] a, int[] b, int[] c, int i, int j, int x){
        // 情况1：a数组已遍历完，将b剩余元素全部加入c
        if(i >= a.length){
            while(j < b.length){
                c[x++] = b[j++];
            }
            return c;
        }
        // 情况2：b数组已遍历完，将a剩余元素全部加入c
        if(j >= b.length){
            while(i < a.length){
                c[x++] = a[i++];
            }
            return c;
        }
        // 情况3：a当前元素更小，加入c后递归处理a的下一个元素
        if(a[i] < b[j]){
            c[x] = a[i];
            combineArray(a, b, c, i + 1, j, x + 1);
        } 
        // 情况4：b当前元素更小或相等，加入c后递归处理b的下一个元素
        else {
            c[x] = b[j];
            combineArray(a, b, c, i, j + 1, x + 1);
        }
        return c;
    }

    public static void main(String [] args) {
        findMe find = new findMe();
        int[] a = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
        int[] b = {4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
        // 你预期结果中的5099不在输入数组内，以下基于你提供的输入处理
        int[] c = new int[a.length + b.length];
        int[] x = find.combineArray(a, b, c, 0, 0, 0);
        // 直接遍历合并后的结果数组
        for(int i = 0; i < x.length; i++){
            System.out.println("On position : " + i + " is value " + x[i]);
        }
    }
}

代码说明 #

• 修正终止条件：用索引与数组长度比较，准确判断遍历是否完成。
• 补充剩余元素处理：通过while循环将未遍历完的数组元素全部追加到结果数组。
• 覆盖元素相等场景：用else分支处理b[j] <= a[i]的情况，确保递归逻辑持续推进。
• 优化main方法：直接使用合并后的结果数组遍历，避免冗余递归调用。

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