如何使用Java Stream合并两个有序整数数组

你当前写的嵌套forEach的嵌套Stream写法完全无法实现需求，核心问题有三个：

• forEach是无返回值的终端操作，调用后流就直接关闭了，根本没法在后头链式调用collect做结果收集
• 这种双层遍历是把两个数组的元素做两两配对的笛卡尔积遍历，既浪费性能（时间复杂度直接到O(n*m)），也完全用不上两个输入数组本身已经有序的前提，根本拼不出顺序正确的结果
• Stream设计上不推荐在遍历过程中维护可变的外部状态（比如双指针的游标、临时结果列表），硬在forEach里改外部变量做比较收集，轻则结果错乱，重则在并行流场景下出现线程安全问题。

可行的实现方案 #

方案1：最简单的常规Stream实现（无嵌套，推荐日常使用） #

不需要搞复杂的嵌套逻辑，直接把两个数组的流拼接到一起做排序就行，代码简洁不容易出错，虽然时间复杂度是O((m+n)log(m+n))，但绝大多数业务场景下性能够用：

import java.util.Arrays;
import java.util.stream.IntStream;

public class SortedArrayMerge {
    public static int[] merge(int[] nums1, int[] nums2) {
        return IntStream.concat(Arrays.stream(nums1), Arrays.stream(nums2))
                .sorted()
                .toArray();
    }

    public static void main(String[] args) {
        int[] a = {1,3,4};
        int[] b = {2,5};
        // 输出结果：[1, 2, 3, 4, 5]
        System.out.println(Arrays.toString(merge(a, b)));
    }
}

方案2：嵌套Stream的O(m+n)复杂度实现（仅做实现参考，不推荐生产用） #

如果一定要用嵌套Stream的形式，同时要利用原数组有序的特性做到线性时间复杂度，可以用递归+Stream.concat做惰性流拼接，本质是把双指针的判断逻辑嵌在流的生成过程里：

import java.util.Arrays;
import java.util.stream.Stream;

public class SortedArrayMerge {
    private static Stream<Integer> buildMergeStream(int[] nums1, int p1, int[] nums2, int p2) {
        // 其中一个数组遍历完，直接返回剩余元素的流
        if (p1 >= nums1.length) return Arrays.stream(nums2).skip(p2).boxed();
        if (p2 >= nums2.length) return Arrays.stream(nums1).skip(p1).boxed();
        
        // 每次取两个指针指向的更小值，递归拼接后续元素的流
        if (nums1[p1] <= nums2[p2]) {
            return Stream.concat(
                    Stream.of(nums1[p1]),
                    buildMergeStream(nums1, p1 + 1, nums2, p2)
            );
        } else {
            return Stream.concat(
                    Stream.of(nums2[p2]),
                    buildMergeStream(nums1, p1, nums2, p2 + 1)
            );
        }
    }

    public static int[] mergeWithNestedStream(int[] nums1, int[] nums2) {
        return buildMergeStream(nums1, 0, nums2, 0)
                .mapToInt(Integer::intValue)
                .toArray();
    }

    public static void main(String[] args) {
        int[] a = {1,3,4};
        int[] b = {2,5};
        // 输出结果：[1, 2, 3, 4, 5]
        System.out.println(Arrays.toString(mergeWithNestedStream(a, b)));
    }
}

补充提示：如果是追求极致性能的场景，别用Stream实现这个需求，直接写传统的双指针遍历合并是最优解，时间复杂度O(m+n)、空间复杂度最低可以做到O(1)（如果结果数组直接复用其中一个输入数组的空间的话），没有Stream的装箱、递归或者排序开销。你最开始想的嵌套forEach的思路从根上就不符合Stream的设计原则，别往这个方向硬写。

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