昨天面试被问到这道算法题,一时没有回答上来,今天思考了一下,参阅了网上的教程,做了一个JAVA版本的实现。
方案一:
新建一个N*L的数组,将原始数组拼接存放在这个大数组中,再调用Arrays.sort()进行排序,或者使用其它排序方法即可。
此方法时间复杂度为o(N*Llog2N*L);
具体代码实现如下:
import java.util.Arrays;
class Solution {
public static int[] MergeArrays(int[][] array) {
int N = array.length, L;
if (N == 0)
return new int[0];
else {
L = array[0].length;
for (int i = 1; i < N; i++)
if (L != array[i].length)
return new int[0];
}
int[] result = new int[N * L];
for (int i = 0; i < N; i++)
for (int j = 0; j < L; j++)
result[i * L + j] = array[i][j];
Arrays.sort(result);
return result;
}
}
方案二:
使用PriorityQueue实现最小堆,需要定义一个指针数组,用于保存这N个数组的index,定义Node类用于保存当前数值(value)和该数字所在的数组序号(idx),并且覆写Comparetor<Node>的compare方法实现自定义排序。PriorityQueue的offer()和poll()方法时间复杂度均为logn。
思路:首先将N个数组的第一位放到PriorityQueue,循环取出优先队列的首位(最小值)放入result数组中,并且插入该首位数字所在数组的下一个数字(如果存在),直到所有数字均被加入到result数组即停止(N*L)次。
时间复杂度:O(N*LlogN)
空间复杂度:O(N)
代码实现:
import java.util.PriorityQueue;
import java.util.Arrays;
import java.util.Comparator;
public class SortedArraysMerge {
static class Node {
int value;
int idx;
public Node(int value, int idx) {
this.value = value;
this.idx = idx;
}
}
public static int[] MergeArrays(int[][] arr) {
int N = arr.length, L;
if (N == 0)//此时传入数组为空
return new int[0];
else {//判断数组是否符合规范
L = arr[0].length;
for (int i = 1; i < N; i++)
if (arr[i].length != L)
return new int[0]; //此时数组不规范
}
int[] result = new int[N * L];
int[] index = new int[N];
Arrays.fill(index, 0, N, 0);
PriorityQueue<Node> queue = new PriorityQueue<Node>(new Comparator<Node>() {
@Override
public int compare(Node n1, Node n2) {
if (n1.value < n2.value)
return -1;
else if (n1.value > n2.value)
return 1;
else
return 0;
}
});
for (int i = 0; i < N; i++) {
Node node = new Node(arr[i][index[i]++], i);
queue.offer(node);
}
System.out.println("" + queue.size());
int idx = 0;
while (idx < N * L) {
Node minNode = queue.poll();
result[idx++] = minNode.value;
if (index[minNode.idx] < L) {
queue.offer(new Node(arr[minNode.idx][index[minNode.idx]], minNode.idx));
index[minNode.idx]++;
}
}
return result;
}
}