LeetCode 面试经典 150 题-分治
分治法
如果只有一个节点，直接作为根；前面的部分是左子树，后面的部分是右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return dfs(nums, 0, nums.length);
}
private TreeNode dfs(int[] nums, int left, int right) {
if (left == right) {
return null;
}
int mid = (left + right) >> 1;
return new TreeNode(nums[mid], dfs(nums, left, mid), dfs(nums, mid + 1, right));
}
}
|
自顶向下归并排序
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
- 对两个子链表分别排序。
- 将两个排序后的子链表合并，得到完整的排序后的链表。
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
|
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = middleNode(head);
ListNode mid = pre.next;
pre.next = null;
head = sortList(head);
mid = sortList(mid);
return merge(head, mid);
}
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode merge(ListNode left, ListNode right) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (left != null && right != null) {
if (left.val < right.val) {
cur.next = left;
left = left.next;
} else {
cur.next = right;
right = right.next;
}
cur = cur.next;
}
cur.next = left != null ? left : right;
return dummy.next;
}
}
|
- 时间复杂度：O(nlogn)
- 空间复杂度：O(logn)
自底向上归并排序
- 遍历链表，获取链表长度 length。
- 初始化步长 step=1。
- 循环直到 step≥length。
- 每轮循环，从链表头节点开始。
- 分割出两段长为 step 的链表，合并，把合并后的链表插到新链表的末尾。重复该步骤，直到链表遍历完毕。
- 把 step 扩大一倍。回到第 4 步。
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
|
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
int len = getLength(head);
ListNode dummy = new ListNode(0);
dummy.next = head;
for (int step = 1; step < len; step *= 2) {
ListNode cur = dummy.next;
ListNode tail = dummy;
while (cur != null) {
ListNode left = cur;
ListNode right = split(left, step);
cur = split(right, step);
tail.next = merge(left, right);
while (tail.next != null) {
tail = tail.next;
}
}
}
return dummy.next;
}
private int getLength(ListNode head) {
int length = 0;
while (head != null) {
length++;
head = head.next;
}
return length;
}
private ListNode split(ListNode head, int size) {
if (head == null) return null;
for (int i = 1; i < size && head.next != null; i++) {
head = head.next;
}
ListNode second = head.next;
head.next = null;
return second;
}
private ListNode merge(ListNode left, ListNode right) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (left != null && right != null) {
if (left.val < right.val) {
cur.next = left;
left = left.next;
} else {
cur.next = right;
right = right.next;
}
cur = cur.next;
}
if (left != null) {
cur.next = left;
} else {
cur.next = right;
}
return dummy.next;
}
}
|
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)
这道题以后再做。
分治法
将链表数组分治成较小的子问题。每次通过中点将数组分成两部分，分别对这两部分递归调用 mergeSort，直到数组只剩下一个链表为止。
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
|
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
if (k == 0) {
return null;
}
return mergeSort(lists, 0, k - 1);
}
public ListNode mergeSort(ListNode[] lists, int left, int right) {
if (left == right) {
return lists[left];
}
int mid = (left + right) >> 1;
return merge(mergeSort(lists, left, mid), mergeSort(lists, mid + 1, right));
}
public ListNode merge(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
while(list1 != null && list2 != null) {
if (list1.val < list2.val) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 != null ? list1 : list2;
return dummy.next;
}
}
|
- 时间复杂度：O(n * k * log(k))
- 空间复杂度：O(logk)
最小堆
维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，可以用优先队列来优化这个过程。
初始把所有链表的头节点入堆，然后不断弹出堆中最小节点 x，如果 x.next 不为空就加入堆中。循环直到堆为空。把弹出的节点按顺序拼接起来，就得到了答案。
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
|
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode node : lists) {
if (node != null) {
pq.offer(node);
}
}
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
if (node.next != null) {
pq.offer(node.next);
}
cur.next = node;
cur = cur.next;
}
return dummy.next;
}
}
|
- 时间复杂度：考虑优先队列中的元素不超过 k 个，那么插入和删除的时间代价为 O(logk)，这里最多有 kn 个点，对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为 O(kn×logk)。
- 空间复杂度：O(k)，优先队列中的元素不超过 k 个。