Algorithms: Divide and Conquer
Published:
- Divide: 将问题划分为一些子问题，子问题的形式和原问题一样，只是规模更小。
- Conquer：递归地求解出子问题。如果子问题的规模足够小，则停止递归进行求解。
- Combine：将子问题的解组合合并成原问题的解
二叉树的DFS中前序、中序、后序遍历实际上都利用了分治思想。
148. Sort List
使用对链表归并排序
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode preHead = ListNode(INT_MIN);
preHead.next = head;
ListNode *preMid = &preHead, *mid = head;
while (head && head->next) {
preMid = mid;
mid = mid -> next;
head = head -> next -> next;
}
preMid -> next = NULL;
return merge(sortList(preHead.next), sortList(mid));
}
ListNode* merge(ListNode* left, ListNode* right) {
ListNode preHead = ListNode(INT_MIN);
ListNode *pt = &preHead;
while (left && right) {
if (left->val < right->val) {
pt -> next = left;
left = left -> next;
} else {
pt -> next = right;
right = right -> next;
}
pt = pt->next;
}
pt->next = left?left:right;
return preHead.next;
}
};
4. Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
- 找出拍好序的2个数组中的第k大元素（此处为找出中点元素）。这个应该更像是二分查找，而不是分治思想，因为每个子问题下只有一个子问题。
- 注意每个子问题的去除k个或m+n-k个元素。 2个数组的2个元素比较，大的数组大的部分去掉， 小的数组小的部分去掉。
A[0], A[1], ... , A[pa-1], ... A[m-1] B[0], B[1], ... , B[pb-1], ... B[n-1] - 其中 B[pb-1], … B[n-1]的长度加上A[0], … , A[pa-1]的长度为k。
- 如果 A[pa-1] > B[pb-1]，仅保留B[pb-1], … B[n-1]和A[0], … , A[pa-1]
- 如果 A[pa-1] < B[pb-1]，仅保留A[pa-1], … A[m-1]和B[0], B[1], … , B[pb-1]
- 如果 A[pa-1] == B[pb-1]，返回A[pa-1]
class Solution {
public:
// common solutin to get the k-th element in sorted array. k belongs to [1, n]
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
int len = m + n;
if (len & 1)
return helper(nums1, nums2, len / 2 + 1);
else
return (helper(nums1, nums2, len / 2) + helper(nums1, nums2, len / 2 + 1)) / 2;
}
double helper(vector<int> nums1, vector<int> nums2, int k) {
int m = nums1.size(), n = nums2.size();
if (m > n) return helper(nums2, nums1, k);
if (m == 0) return nums2[k - 1];
if (k == 1) return min(nums1[0], nums2[0]);
int pa = min(k / 2, m), pb = k - pa;
if (nums1[pa - 1] < nums2[pb - 1]) {
nums1.erase(nums1.begin(), nums1.begin() + pa);
nums2.erase(nums2.begin() + pb, nums2.end());
return helper(nums1, nums2, k - pa);
}
else if (nums2[pb - 1] < nums1[pa - 1]) {
nums2.erase(nums2.begin(), nums2.begin() + pb);
nums1.erase(nums1.begin() + pa, nums1.end());
return helper(nums1, nums2, k - pb);
}
else {
return nums1[pa - 1];
}
}
};