-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathmergeKSortedArray.java
More file actions
56 lines (44 loc) · 1.52 KB
/
mergeKSortedArray.java
File metadata and controls
56 lines (44 loc) · 1.52 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//This is a classic interview question. Another similar problem is "merge k sorted lists".
//This problem can be solved by using a HEAP. The time is O(nlog(n)).
//Given m arrays, the minimum elements of all arrays can form a heap. It takes O(log(m)) to insert an element to the heap and it takes O(1) to delete the minimum element.
//At first, write comparator class
class ArrayContainer implements Comparable<ArrayContainer> {
int[] arr;
int index;
public ArrayContainer(int[] arr, int index) {
this.arr = arr;
this.index = index;
}
@Override
public int compareTo(ArrayContainer o) {
if (this.arr[this.index] > o.arr[o.index]) {
return 1;
} else if (this.arr[this.index] < o.arr[o.index]) {
return -1;
} else {
return 0;
}
}
}
//Handle merged sorted arrays
public static int[] mergeKSortedArray(int[][] arr) {
//PriorityQueue is heap in Java
PriorityQueue<ArrayContainer> queue = new PriorityQueue<ArrayContainer>();
int total=0;
//add arrays to heap
for (int i = 0; i < arr.length; i++) {
queue.add(new ArrayContainer(arr[i], 0));
total = total + arr[i].length;
}
int m=0;
int result[] = new int[total];
//while heap is not empty
while(!queue.isEmpty()){
ArrayContainer ac = queue.poll();
result[m++]=ac.arr[ac.index];
if(ac.index < ac.arr.length-1){
queue.add(new ArrayContainer(ac.arr, ac.index+1));
}
}
return result;
}