Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitcbbbced

Browse files
committed
023 (3) add divide & conquer solution
1 parentc5e5f49 commitcbbbced

File tree

4 files changed

+92
-95
lines changed

4 files changed

+92
-95
lines changed

‎src/_023_MergeKSortedLists/Solution.java

Lines changed: 29 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -14,43 +14,44 @@
1414
*/
1515
package_023_MergeKSortedLists;
1616

17-
importjava.util.Comparator;
18-
importjava.util.PriorityQueue;
19-
importjava.util.Queue;
20-
2117
importcom.leetcode.ListNode;
2218

2319
/** see test {@link _023_MergeKSortedLists.SolutionTest } */
2420
publicclassSolution {
2521

22+
// divide and conquer, merge two lists at one time
2623
publicListNodemergeKLists(ListNode[]lists) {
27-
ListNodedummy =newListNode(0);
28-
ListNodenode =dummy;
29-
30-
Queue<ListNode>queue =newPriorityQueue<>(newComparator<ListNode>() {
31-
@Override
32-
publicintcompare(ListNodeo1,ListNodeo2) {
33-
returno1.val -o2.val;
34-
}
35-
});
36-
37-
// push all heads into queue
38-
for (ListNodehead :lists) {
39-
if (head !=null) {
40-
queue.add(head);
41-
}
24+
returnmergeKLists(lists,0,lists.length -1);
25+
}
26+
27+
// divide and conquer
28+
privateListNodemergeKLists(ListNode[]lists,intleft,intright) {
29+
if (left <right) {
30+
intmid =left + (right -left) /2;
31+
returnmergeTwo(mergeKLists(lists,left,mid),mergeKLists(lists,mid +1,right));
32+
}elseif (left ==right) {
33+
returnlists[left];
34+
}else {
35+
returnnull;
4236
}
43-
44-
// choose next node from k candidates
45-
while (!queue.isEmpty()) {
46-
ListNodecur =queue.poll();
47-
node.next =cur;
48-
if (cur.next !=null) {
49-
queue.add(cur.next);
37+
}
38+
39+
// merge two lists
40+
privateListNodemergeTwo(ListNodelist1,ListNodelist2) {
41+
ListNodedummy =newListNode(0);
42+
ListNodecur =dummy;
43+
while (list1 !=null &&list2 !=null) {
44+
if (list1.val <list2.val) {
45+
cur.next =list1;
46+
list1 =list1.next;
47+
}else {
48+
cur.next =list2;
49+
list2 =list2.next;
5050
}
51-
node =node.next;
51+
cur =cur.next;
5252
}
53-
returndummy.next;
53+
cur.next =list1 !=null ?list1 :list2;
54+
returndummy.next;
5455
}
5556

5657
}

‎src/_023_MergeKSortedLists/Solution2.java

Lines changed: 0 additions & 63 deletions
This file was deleted.
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
/**
2+
* Time : O(NlgN) ; Space: O(N)
3+
* @tag : Divide and Conquer; Linked List; Heap
4+
* @by : Steven Cooks
5+
* @date: Sep 1, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
* Merge k sorted linked lists and return it as one sorted list. Analyze
10+
* and describe its complexity.
11+
*
12+
***************************************************************************
13+
* {@link https://leetcode.com/problems/merge-k-sorted-lists/ }
14+
*/
15+
package_023_MergeKSortedLists;
16+
17+
importjava.util.Comparator;
18+
importjava.util.PriorityQueue;
19+
importjava.util.Queue;
20+
21+
importcom.leetcode.ListNode;
22+
23+
/** see test {@link _023_MergeKSortedLists.SolutionHeapTest } */
24+
publicclassSolutionHeap {
25+
26+
// For next number, we want to find the smallest number from k lists' heads.
27+
// The best data structure to know max/min from k elements is heap
28+
publicListNodemergeKLists(ListNode[]lists) {
29+
ListNodedummy =newListNode(0);
30+
ListNodenode =dummy;
31+
32+
// stores head node of k merging lists
33+
Queue<ListNode>queue =newPriorityQueue<>(newComparator<ListNode>() {
34+
@Override
35+
publicintcompare(ListNodeo1,ListNodeo2) {
36+
returno1.val -o2.val;
37+
}
38+
});
39+
40+
// push all heads into queue
41+
for (ListNodehead :lists) {
42+
if (head !=null) {
43+
queue.add(head);
44+
}
45+
}
46+
47+
// choose next node from k candidates
48+
while (!queue.isEmpty()) {
49+
ListNodecur =queue.poll();
50+
node.next =cur;
51+
if (cur.next !=null) {
52+
queue.add(cur.next);
53+
}
54+
node =node.next;
55+
}
56+
returndummy.next;
57+
}
58+
59+
}

‎test/_023_MergeKSortedLists/Solution2Test.javarenamed to‎test/_023_MergeKSortedLists/SolutionHeapTest.java

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -12,17 +12,17 @@
1212

1313
importcom.leetcode.ListNode;
1414

15-
publicclassSolution2Test {
15+
publicclassSolutionHeapTest {
1616

17-
/** Test method for {@link _023_MergeKSortedLists.Solution2 } */
18-
Solution2solution;
17+
/** Test method for {@link _023_MergeKSortedLists.SolutionHeap } */
18+
SolutionHeapsolution;
1919

2020
@Rule
2121
publicTimeoutglobalTimeout =newTimeout(200);
2222

2323
@Before
2424
publicvoidsetUp()throwsException {
25-
solution =newSolution2();
25+
solution =newSolutionHeap();
2626
}
2727

2828
@After

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp