-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution23.java
More file actions
248 lines (231 loc) · 6.67 KB
/
Copy pathSolution23.java
File metadata and controls
248 lines (231 loc) · 6.67 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
import java.util.StringJoiner;
import static util.Asserts.assertArrayEquals;
import static util.Asserts.assertEquals;
import static util.Asserts.assertNotNull;
/**
* <pre>
* 23. 合并K个升序链表
*
* 难度：困难
*
* 给你一个链表数组，每个链表都已经按升序排列。
*
* 请你将所有链表合并到一个升序链表中，返回合并后的链表。
*
*
*
* 示例 1：
*
* 输入：lists = [[1,4,5],[1,3,4],[2,6]]
* 输出：[1,1,2,3,4,4,5,6]
* 解释：链表数组如下：
* [
* 1->4->5,
* 1->3->4,
* 2->6
* ]
* 将它们合并到一个有序链表中得到。
* 1->1->2->3->4->4->5->6
*
* 示例 2：
*
* 输入：lists = []
* 输出：[]
*
* 示例 3：
*
* 输入：lists = [[]]
* 输出：[]
*
*
*
* 提示：
*
* k == lists.length
* 0 <= k <= 10^4
* 0 <= lists[i].length <= 500
* -10^4 <= lists[i][j] <= 10^4
* lists[i] 按 升序 排列
* lists[i].length 的总和不超过 10^4
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode.cn/problems/merge-k-sorted-lists
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* </pre>
*
* @author abomb4 2022-10-12 22:21:22
*/
public class Solution23 {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
SmallHeap heap = new SmallHeap(32 - Integer.numberOfLeadingZeros(lists.length));
for (ListNode node : lists) {
if (node != null) {
heap.add(node);
}
}
ListNode head = null;
ListNode current = null;
while (heap.size > 0) {
final ListNode peek = heap.replaceTopNode();
if (peek == null) {
break;
}
if (head == null) {
head = peek;
current = head;
} else {
current.next = peek;
current = current.next;
}
}
return head;
}
public static class SmallHeap {
ListNode[] base;
int size = 0;
SmallHeap(int level) {
// 1: root only
// 2: 3 nodes
base = new ListNode[(int)Math.pow(2, level) - 1];
}
public void add(ListNode node) {
base[size] = node;
shiftUp(size);
size += 1;
}
ListNode peek() {
if (size == 0) {
return null;
}
return base[0];
}
ListNode replaceTopNode() {
if (size == 0) {
return null;
}
ListNode top = base[0];
ListNode next = top.next;
if (top.next == null) {
// remove top
swap(0, size - 1);
size -= 1;
if (size > 0) {
shiftDown(0);
}
} else {
base[0] = next;
if (top.val != next.val) {
shiftDown(0);
}
}
return top;
}
void shiftDown(int index) {
int downTo = index;
final int leftIndex = indexLeftChild(index);
if (leftIndex < size && base[leftIndex].val < base[downTo].val) {
downTo = leftIndex;
}
final int rightIndex = indexRightChild(index);
if (rightIndex < size && base[rightIndex].val < base[downTo].val) {
downTo = rightIndex;
}
if (downTo != index) {
swap(downTo, index);
shiftDown(downTo);
}
}
void shiftUp(int index) {
int parentIndex = indexParent(index);
if (parentIndex == -1) {
return;
}
int parentVal = base[parentIndex].val;
int thisVal = base[index].val;
if (parentVal > thisVal) {
swap(parentIndex, index);
shiftUp(parentIndex);
}
}
void swap(int i1, int i2) {
final ListNode tmp = base[i1];
base[i1] = base[i2];
base[i2] = tmp;
}
static int indexParent(int index) {
return index == 0 ? -1 : (index - 1) / 2;
}
static int indexLeftChild(int index) {
return index * 2 + 1;
}
static int indexRightChild(int index) {
return index * 2 + 2;
}
}
public static void main(String[] args) {
final Solution23 s = new Solution23();
{
String in = "[[1,4,5],[1,3,4],[2,6]]";
String expect = "[1,1,2,3,4,4,5,6]";
final ListNode result = s.mergeKLists(toNodes(in));
final String real = toString(result);
assertEquals(expect, real, "in: " + in);
}
{
String in = "[[]]";
String expect = "[]";
final ListNode result = s.mergeKLists(toNodes(in));
final String real = toString(result);
assertEquals(expect, real, "in: " + in);
}
System.out.println("OK");
}
static String toString(ListNode node) {
if (node == null) {
return "[]";
}
final StringJoiner sb = new StringJoiner(",", "[", "]");
ListNode current = node;
while (current != null) {
sb.add(String.valueOf(current.val));
current = current.next;
}
return sb.toString();
}
static ListNode[] toNodes(String in) {
final String sub = in.substring(2, in.length() - 2);
final String[] groups = sub.split("],\\[");
final ListNode[] result = new ListNode[groups.length];
for (int i = 0; i < groups.length; i++) {
String group = groups[i];
if (group == null || group.isEmpty()) {
continue;
}
final String[] nums = group.split(",");
ListNode root = null;
ListNode current = null;
for (String str : nums) {
final int num = Integer.parseInt(str);
if (root == null) {
root = new ListNode(num);
current = root;
} else {
current.next = new ListNode(num);
current = current.next;
}
}
result[i] = root;
}
return result;
}
static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
}