之前没钻研过LeetCode，上次做题时，以为要找什么类型的题目就在搜索栏输入对应的关键词，结果输入divide-and-conquer才搜到一题，后来经提醒才知道在网页右侧有个提供各种关键词的topics框部，点击了divide-and-conquer便搜到了好多道相关题目，方便许多。之前真是太蠢了。
这次选择的是第4题：Median of Two Sorted Arrays 难度系数为Hard。
题目要求如下：
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
最先想到的、即最容易的方法便是将两个数组合并，重新排序，然后根据奇偶顺利找出中位数。代码如下：
class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();vector<int> All_array;//将两个数组合并All_array.assign(nums1.begin(), nums1.end());All_array.insert(All_array.end(), nums2.begin(), nums2.end());//将合并后的数组进行排序sort(All_array.begin(), All_array.end());return (m+n)%2?All_array[(m+n)/2]:(All_array[(m+n)/2-1]+All_array[(m+n)/2])/2.0;}
};
然而此题的难度便在于题目要求将时间复杂度限制在O(log(m+n))，也就是在暗示我们采取分治法。首先保持两个原数组不变，相当于首次一分为二。那么接下来要怎么再逐步分下去呢？我们可以想办法将所有的数据分为两部分：1 含有中位数的部分数据； 2 不含中位数的部分数据。然后将没用的第2部分数据抛弃，再将有用的第1部分数据继续递归分裂，直至筛选出中位数。
那么问题来了。
将所有数据分为两部分，如何确定中位数存在于哪部分呢？
我们也可以将该问题扩展，设0<k<m+n，将所有数据分为两部分，那如何确定第k大的数存在于哪部分呢？我们将这个第k大的数字称为“int_K”。
【以下皆按正常情况进行讨论】
首先，两个数组都是已排序好的。在所有的数据中，若按从小到大进行排序，int_K前面应有k-1个数。
我们在nums1中取nums1[0]到nums1[k/2-1]共k/2个整数（从小到大），在nums2中取nums2[0]到nums2[k/2-1]共k/2个整数（从小到大）。
【反证法】 若nums1[k/2-1]≥nums1[k/2-1]，如果int_K存在于nums2[0]~nums2[k/2-1]之中，那么所有数据按大小，排在int_K前面的仅可能是nums1[0]~nums1[k/2-2]和nums2[0]~nums2[k/2-2]，加起来的总数绝不超过k-1，这与“int_K前面应有k-1个数”矛盾。故int_K不存在于nums2[0]到nums2[k/2-1]之中，可将这部分数据抛弃。反之如此。
按此思路，代码如下：
class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();if ((m + n) % 2) return find_kth_SortedArrays(nums1, nums2, (m + n) / 2 + 1);elsereturn (find_kth_SortedArrays(nums1, nums2, (m + n) / 2) + find_kth_SortedArrays(nums1, nums2, (m + n) / 2 + 1)) / 2.0;}int find_kth_SortedArrays(vector<int> nums1, vector<int> nums2, int k) {int m = nums1.size();int n = nums2.size();if (m > n)return find_kth_SortedArrays(nums2, nums1, k);if (m == 0)return nums2[k - 1];if (k == 1)return min(nums1[0], nums2[0]);int temp1 = min(m, k/2);int temp2 = min(n, k/2);if (nums1[temp1 - 1] >= nums2[temp2 - 1]) {return find_kth_SortedArrays(nums1, vector<int>(nums2.begin() + temp2, nums2.end()), k - temp2);} else {return find_kth_SortedArrays(vector<int>(nums1.begin() + temp1, nums1.end()), nums2, k - temp1);}return 0;}
};另外我又尝试了别的方法，也是寻找第k位大的数。该方法即针对每个选定的数据，判断在所有的数据当中，是否存在k-1个数字小于等于它，其他的数字都大于等于它。若是，则返回该数据。代码如下（根据多种情况不停填补修改 所以代码看着有点乱= =）
class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();return (find_kth_SortedArrays(nums1, nums2, (m + n + 1) / 2) + find_kth_SortedArrays(nums1, nums2, (m + n + 2) / 2)) / 2.0;}int find_kth_SortedArrays(vector<int> nums1, vector<int> nums2, int k) {int m = nums1.size();int n = nums2.size();if (m == 0)return nums2[k - 1];if (n == 0)return nums1[k - 1];if (k == 1)return min(nums1[0], nums2[0]);int i;for (i = 0; i < m; i++) {if (k-1-i-1 >= 0 && k-1-i-1 < n && nums2[k-1-i-1] <= nums1[i]) {if (k-1-i >= n)return nums1[i];else if (nums2[k-1-i] >= nums1[i])return nums1[i];}if (k == i + 1 && nums2[0] >= nums1[i])return nums1[i];}for (i = 0; i < n; i++) {if (k-1-i-1 >= 0 && k-1-i-1 < m && nums1[k-1-i-1] <= nums2[i]) {if (k-1-i >= m)return nums2[i];else if (nums1[k-1-i] >= nums2[i])return nums2[i];}if (k == i + 1 && nums1[0] >= nums2[i])return nums2[i];}}
};