題目描述：給兩個有序數(shù)組，找出這些數(shù)的中位數(shù)评腺。要求復(fù)雜度O(log (m+n))杈女。
分析：一般化的問題是找所有數(shù)中第K大的數(shù)『阑澹可以根據(jù)歸并排序中merge的思路合并兩個數(shù)組在取第K大的值顶捷，復(fù)雜度O(m + n)。方法一在這個思路上改進一點屎篱，不排序而只設(shè)計數(shù)器記下當(dāng)前已找到第x大的數(shù)服赎，復(fù)雜度仍然是O(m + n)葵蒂。方法二根據(jù)排序特性利用二分來解決，每次可刪除k/2的元素重虑，方法三是其非遞歸找中位數(shù)版践付，復(fù)雜度都是O(log (m+n))。
方法一：時空復(fù)雜度都是O(m + n)缺厉，還是可以過OJ永高。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int l1 = nums1.size(), l2 = nums2.size();
int cnt = l1 + l2, mid = cnt / 2;
int e = !(cnt % 2); //設(shè)標(biāo)志總個數(shù)是否為偶數(shù)使兩種情況統(tǒng)一處理，e == 1為偶數(shù)芽死，返回(v[mid] + v[mid - e]) / 2.0; e == 0為奇數(shù)乏梁，返回(v[mid] + v[mid - e]) / 2.0。
if (l1 == 0) return (nums2[mid] + nums2[mid - e]) / 2.0;
if (l2 == 0) return (nums1[mid] + nums1[mid - e]) / 2.0;
vector<int> v;
int i = 0, j = 0, k;
for (k = 0; k <= mid; k ++)
{
//錯誤處1关贵，i >= l可能導(dǎo)致訪問過界遇骑，設(shè)為最大整數(shù)值即可
int a = i < l1? nums1[i] : INT_MAX;
int b = j < l2? nums2[j] : INT_MAX;
if (a < b)
v.push_back(nums1[i ++]); //錯誤處2，不能用下標(biāo)v[k++]在尾部追加賦值
else
v.push_back(nums2[j ++]);
}
return (v[mid] + v[mid - e]) / 2.0;
}
};
出現(xiàn)錯誤“reference binding to null pointer of type 'value_type'”的原因見代碼注釋1 揖曾、 2兩處落萎。主要是vector與數(shù)組的區(qū)別，動態(tài)分配內(nèi)存所以不能用下標(biāo)方式追加數(shù)炭剪。
方法二：通用的用分治法找第K大的數(shù)练链。設(shè)l = nums.size()可發(fā)現(xiàn)如下規(guī)律：
- 若l % 2 == 1，數(shù)組中位數(shù) = 第 (l + 1) / 2 大的數(shù) = 第(l + 2) / 2大數(shù) = （第 (l + 1) / 2 大的數(shù) + 第(l + 2) / 2大數(shù) ）/ 2
- 若l % 2 == 0奴拦，數(shù)組中位數(shù) = （第 (l + 1) / 2 大的數(shù) + 第(l + 2) / 2大數(shù) ）/ 2
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int l1 = nums1.size(), l2 = nums2.size();
//調(diào)用查找第K大函數(shù)媒鼓，不是下標(biāo)
return (findKth(nums1, nums2, (l1 + l2 + 1) / 2) + findKth(nums1, nums2, (l1 + l2 + 2) / 2)) / 2.0;
}
int findKth(vector<int> nums1, vector<int> nums2, int k)
{
int l1 = nums1.size(), l2 = nums2.size();
//固定nums1的長度較短，減少判斷情況
if (l1 > l2) return findKth(nums2, nums1, k);
if (l1 == 0) return nums2[k - 1];
if (k == 1) return min(nums1[0], nums2[0]);
//統(tǒng)一數(shù)組長度小于k / 2的情況错妖。
int i = min(l1, k/2), j = min(l2, k / 2);
//nums2的前j - 1（不超過k / 2）個數(shù)都是所有數(shù)的前k / 2小的數(shù)中的元素绿鸣，可排除
if (nums1[i - 1] > nums2[j - 1])
return findKth(nums1, vector<int>(nums2.begin() + j, nums2.end()), k - j); //nums2的前j個數(shù)一定在k之前，所以在剩下的數(shù)中找第k - j大的數(shù)
else
return findKth(vector<int>(nums1.begin() + i, nums1.end()), nums2, k - i);
//return 0;
}
};
方法三：設(shè)l = nums.size()可發(fā)現(xiàn)如下規(guī)律：
- 若l % 2 == 1暂氯，數(shù)組中位數(shù) = nums[l / 2] = nums[(l - 1) / 2] = （nums[l / 2] + nums[(l - 1) / 2]）/ 2
- 若l % 2 == 0潮模，數(shù)組中位數(shù) = （nums[l / 2] + nums[(l - 1) / 2]）/ 2
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2 = nums2.size();
//保證nums1最短
if (len1 > len2)
return findMedianSortedArrays(nums2, nums1);
if (len1 == 0)
return (nums2[(len2 - 1) / 2] + nums2[len2 / 2]) / 2.0;
int l = 0, r = len1 * 2; //nums1較短，故中位數(shù)一定在len1及其后
int l1, l2, r1, r2;
while(l <= r)
{
int mid1 = (l + r) / 2; //第一次分mid1 = len1
int mid2 = len1 + len2 - mid1; /第一次分mid2 = len2
//mid1 = 0 —— 數(shù)組1整體都比中值大痴施，l1 > r2擎厢，中值在2中
l1 = (mid1 == 0)? INT_MIN : nums1[(mid1 - 1) / 2]; //第一次割一定在nums1的中位數(shù)上
r1 = (mid1 == 2 * len1)? INT_MAX : nums1[mid1 / 2];
//mid2 = 0 —— 數(shù)組2整體都比中值大，l2 > r1辣吃，中值在1中
l2 = (mid2 == 0)? INT_MIN : nums2[(mid2 - 1) / 2]; //第一次割一定在nums2的中位數(shù)上
r2 = (mid2 == 2 * len2)? INT_MAX : nums2[mid2 / 2];
if(l1 > r2) //說明中位數(shù)在數(shù)組一的更前半部或數(shù)組二的更后半部动遭，故減小mid1，增大mid2神得。說明數(shù)組一的后半部不用找了
r = mid1 - 1;
else if(l2 > r1) //說明中位數(shù)在數(shù)組二的更前半部或數(shù)組一的更后半部厘惦，故減小mid2，增大mid1循头。說明數(shù)組一的前半部不用找了
l = mid1 + 1;
else //l1 < r2 && l2 < r1绵估，又因為找的是中位數(shù)，故兩個割分別在兩序列中間卡骂。說明Max(l1, l2)就是中位數(shù)国裳。
break;
}
//當(dāng)兩數(shù)組數(shù)字總個數(shù)為奇數(shù)時，割將個數(shù)為奇數(shù)的那個數(shù)組的中位數(shù)分為兩個全跨，故max(l1, l2) = min(r1, r2)
return (max(l1, l2)+ min(r1, r2))/2.0;
}
};
