有100个已排序数组，先需要合并为一个排序数组如何实现？数组长度在10w ~40w间

public static void main(String[] args){
    int[][] arrs = new int[][]{
            {1, 3, 4},
            {1, 2, 5},
            {0, 7, 5, 8}
    };

    int[] result = merge(arrs);

    for(int num : result){
        System.out.print(num+" ");
    }
}


private static int getAllCount(int[][] arrs){
    int size = 0;
    for(int[] item : arrs){
        if(item == null) continue;
        size += item.length;
    }
    return size;
}

private static int[] getArrayIdxsAndSet_0(int size){
    int[] idxs = new int[size];
    // 初始化为零
    for(int i = 0; i < idxs.length; i++){
        idxs[i] = 0;
    }
    return idxs;
}

public static int[] merge(int[][] arrs)  {
    if(arrs == null) return null;

    int allCount = getAllCount(arrs);

    int[] result = new int[allCount];
    int[] arrayIdxs = getArrayIdxsAndSet_0(arrs.length);

    for(int resultIdx = 0; resultIdx < allCount; resultIdx++){

        int minValue = 0;
        int minArrayIdx = 0;
        boolean tempNotSet = true;

        for(int i = 0; i < arrs.length; i++){
            int currentIdx = arrayIdxs[i];

            if(currentIdx < arrs[i].length){
                if(tempNotSet){
                    tempNotSet = false;
                    minValue = arrs[i][currentIdx];
                    minArrayIdx = i;
                }else if(minValue > arrs[i][currentIdx]) {
                    minValue = arrs[i][currentIdx];
                    minArrayIdx = i;
                }
            }
        }

        arrayIdxs[minArrayIdx]++;
        result[resultIdx] = minValue;
    }

    return result;
}
打赏
Post Views: 453