[算法] - 合并N个有序数组

1. 代码

package com.jfp;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author jiafupeng
 * @desc
 * @create 2021/3/17 16:59
 * @update 2021/3/17 16:59
 **/
public class Test4 {

    public static int[] merge(int[] arr1, int[] arr2) {
        int m = 0;
        int n = 0;
        int[] mergeArr = new int[arr1.length + arr2.length];

        int i = 0;
        while (m < arr1.length || n < arr2.length) {
            if(m >= arr1.length){
                mergeArr[i++] = arr2[n++];
            } else if(n >= arr2.length){
                mergeArr[i++] = arr1[m++];
            } else if(arr1[m] < arr2[n]){
                mergeArr[i++] = arr1[m++];
            } else {
                mergeArr[i++] = arr2[n++];
            }
        }

        return mergeArr;
    }

    public static int[] mergeAll(ArrayList<int[]> lists, int l, int r){
        if(l >= r){
            return lists.get(l);
        }

        int m = (l + r) /2;
        int[] left = mergeAll(lists, l, m);
        int[] right = mergeAll(lists, m+1, r);
        return merge(left, right);
    }

    public static void main(String[] args) {
        int[] arr1 = {2,3,5,20};
        int[] arr2 = {2,4,6,8,10,12};
        int[] arr3 = {1,9,11};
        ArrayList<int[]> list = new ArrayList<>();
        list.add(arr1);
        list.add(arr2);
        list.add(arr3);
        int[] merge = mergeAll(list, 0, list.size() -1);
        System.out.println(Arrays.toString(merge));
    }
}

2. 输出

[1, 2, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 20]