Skip to content

Commit dce5a72

Browse files
Serena211Serena211
committed
may.8 merge
1 parent aa82964 commit dce5a72

10 files changed

Lines changed: 196 additions & 0 deletions

‎bin/Class21_Advanced3/Element.class‎

456 Bytes
Binary file not shown.

‎bin/Class21_Advanced3/ListBuilder.class‎

821 Bytes
Binary file not shown.

‎bin/Class21_Advanced3/MergeKSortedArray$1.class‎

1.07 KB
Binary file not shown.

‎bin/Class21_Advanced3/MergeKSortedArray.class‎

2.08 KB
Binary file not shown.

‎bin/Class21_Advanced3/MergeKSortedLists$1.class‎

1.21 KB
Binary file not shown.

‎bin/Class21_Advanced3/MergeKSortedLists$Element.class‎

579 Bytes
Binary file not shown.

‎bin/Class21_Advanced3/MergeKSortedLists.class‎

2.82 KB
Binary file not shown.

‎src/Class21_Advanced3/ListBuilder.java‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package Class21_Advanced3;
2+
3+
import Class05_BFS_Graph.ListNode;
4+
5+
public class ListBuilder {
6+
public ListNode listBuilder(int[] array) {
7+
if (array == null || array.length == 0) {
8+
return null;
9+
}
10+
ListNode dummy = new ListNode(0);
11+
ListNode cur = dummy;
12+
for (int i = 0; i < array.length; i++) {
13+
cur.next = new ListNode(array[i]);
14+
cur = cur.next;
15+
16+
}
17+
return dummy.next;
18+
19+
}
20+
public static void main(String[] args) {
21+
// TODO Auto-generated method stub
22+
// ListBuilder list = new ListBuilder();
23+
// ListNode list1 = list.listBuilder(new int[]{1,3,5,6,8});
24+
25+
// ListNode list2 = list.listBuilder(new int[]{1,3,4,0,8});
26+
// while (list2 != null) {
27+
// System.out.println(list2.value);
28+
// list2 = list2.next;
29+
// }
30+
31+
}
32+
33+
}

‎src/Class21_Advanced3/MergeKSortedArray.java‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
package Class21_Advanced3;
2+
3+
import java.util.Arrays;
4+
import java.util.Comparator;
5+
import java.util.PriorityQueue;
6+
7+
/*
8+
* Merge K sorted array into one big sorted array in ascending order.
9+
*
10+
* Assumptions
11+
* The input arrayOfArrays is not null, none of the arrays is null either.
12+
*/
13+
class Element {
14+
public int val;
15+
public int rowNum;
16+
public int colNum;
17+
18+
public Element(int v, int r, int c) {
19+
val = v;
20+
rowNum = r;
21+
colNum = c;
22+
}
23+
}
24+
25+
public class MergeKSortedArray {
26+
27+
public int[] merge(int[][] arrayOfArrays) {
28+
int N = arrayOfArrays.length;
29+
if (N == 0) {
30+
return new int[0];
31+
}
32+
int[] M = new int[N];
33+
int length = 0;
34+
for (int i = 0; i < N; i++) {
35+
M[i] = arrayOfArrays[i].length;
36+
length += M[i];
37+
}
38+
39+
int[] rsl = new int[length];
40+
41+
Comparator<Element> ElementComparator = new Comparator<Element>() {
42+
43+
@Override
44+
public int compare(Element o1, Element o2) {
45+
if (o1.val == o2.val) {
46+
return 0;
47+
}
48+
return o1.val < o2.val ? -1 : 1;
49+
}
50+
};
51+
PriorityQueue<Element> min = new PriorityQueue<Element>(N,
52+
ElementComparator);
53+
54+
for (int r = 0; r < N; r++) {
55+
if (M[r] != 0) {
56+
min.offer(new Element(arrayOfArrays[r][0], r, 0));
57+
}
58+
}
59+
for (int i = 0; i < rsl.length; i++) {
60+
Element temp = min.peek();
61+
rsl[i] = temp.val;
62+
min.poll();
63+
64+
// add next element of corresponding sorted array
65+
if (temp.colNum + 1 < M[temp.rowNum]) {
66+
min.offer(new Element(
67+
arrayOfArrays[temp.rowNum][temp.colNum + 1],
68+
temp.rowNum, temp.colNum + 1));
69+
}
70+
}
71+
return rsl;
72+
}
73+
74+
public static void main(String[] args) {
75+
MergeKSortedArray sol = new MergeKSortedArray();
76+
int[][] array = new int[][]{{4,5},{},{1,2,5,9}};
77+
System.out.println(Arrays.toString(sol.merge(array)));
78+
}
79+
80+
}

‎src/Class21_Advanced3/MergeKSortedLists.java‎

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
package Class21_Advanced3;
2+
3+
import java.util.ArrayList;
4+
import java.util.Comparator;
5+
import java.util.List;
6+
import java.util.PriorityQueue;
7+
8+
import Class05_BFS_Graph.ListNode;
9+
10+
/*
11+
* Merge K sorted lists into one big sorted list in ascending order.
12+
*
13+
* Assumptions
14+
* ListOfLists is not null, and none of the lists is null.
15+
*/
16+
17+
public class MergeKSortedLists {
18+
static class Element {
19+
public int val;
20+
public ListNode node;
21+
public Element(int v, ListNode n) {
22+
val = v;
23+
node = n;
24+
}
25+
}
26+
public ListNode merge(List<ListNode> listOfLists) {
27+
if (listOfLists.size() == 0) {
28+
return null;
29+
}
30+
int K = listOfLists.size(); // count how many sorted lists
31+
ListNode dummyNode = new ListNode(0);
32+
ListNode cur = dummyNode;
33+
Comparator<Element> listComparator = new Comparator<Element>() {
34+
35+
36+
@Override
37+
public int compare(Element o1, Element o2) {
38+
if (o1.val == o2.val) {
39+
return 0;
40+
}
41+
return o1.val < o2.val ? -1 : 1;
42+
}
43+
};
44+
PriorityQueue<Element> min = new PriorityQueue<Element>(K, listComparator);
45+
46+
for (int i = 0; i < K; i++) {
47+
if (listOfLists.get(i) != null) {
48+
min.offer(new Element(listOfLists.get(i).value,listOfLists.get(i)));
49+
}
50+
}
51+
while (!min.isEmpty()) {
52+
Element temp = min.peek();
53+
cur.next = temp.node;
54+
cur = cur.next;
55+
min.poll();
56+
57+
// add next node into priority queue
58+
if (temp.node.next != null) {
59+
min.offer(new Element(temp.node.next.value, temp.node.next));
60+
}
61+
}
62+
return dummyNode.next;
63+
}
64+
65+
public static void main(String[] args) {
66+
MergeKSortedLists sol = new MergeKSortedLists();
67+
ListBuilder list = new ListBuilder();
68+
ListNode list1 = list.listBuilder(new int[]{1,3,5,6,8});
69+
ListNode list2 = list.listBuilder(new int[]{1,10});
70+
ListNode list3 = list.listBuilder(new int[]{0,2,7});
71+
List<ListNode> lists = new ArrayList<ListNode>();
72+
lists.add(list1);
73+
lists.add(list2);
74+
lists.add(list3);
75+
ListNode rsl = sol.merge(lists);
76+
while (rsl != null) {
77+
System.out.println(rsl.value);
78+
rsl = rsl.next;
79+
}
80+
// System.out.println(sol.merge(lists));
81+
}
82+
83+
}

0 commit comments

Comments
 (0)