有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;
}
打赏