4. Median of Two Sorted Arrays
2017-10-19 本文已影响0人
Nautilus1
题目描述：给两个有序数组，找出这些数的中位数。要求复杂度O(log (m+n))。
分析：一般化的问题是找所有数中第K大的数。可以根据归并排序中merge的思路合并两个数组在取第K大的值，复杂度O(m + n)。方法一在这个思路上改进一点，不排序而只设计数器记下当前已找到第x大的数，复杂度仍然是O(m + n)。方法二根据排序特性利用二分来解决，每次可删除k/2的元素，方法三是其非递归找中位数版，复杂度都是O(log (m+n))。
方法一：时空复杂度都是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); //设标志总个数是否为偶数使两种情况统一处理，e == 1为偶数，返回(v[mid] + v[mid - e]) / 2.0; e == 0为奇数，返回(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可能导致访问过界，设为最大整数值即可
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，不能用下标v[k++]在尾部追加赋值
else
v.push_back(nums2[j ++]);
}
return (v[mid] + v[mid - e]) / 2.0;
}
};
出现错误“reference binding to null pointer of type 'value_type'”的原因见代码注释1 、 2两处。主要是vector与数组的区别，动态分配内存所以不能用下标方式追加数。
方法二：通用的用分治法找第K大的数。设l = nums.size()可发现如下规律：
- 若l % 2 == 1，数组中位数 = 第 (l + 1) / 2 大的数 = 第(l + 2) / 2大数 = （第 (l + 1) / 2 大的数 + 第(l + 2) / 2大数 ）/ 2
- 若l % 2 == 0，数组中位数 = （第 (l + 1) / 2 大的数 + 第(l + 2) / 2大数 ）/ 2
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int l1 = nums1.size(), l2 = nums2.size();
//调用查找第K大函数，不是下标
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]);
//统一数组长度小于k / 2的情况。
int i = min(l1, k/2), j = min(l2, k / 2);
//nums2的前j - 1（不超过k / 2）个数都是所有数的前k / 2小的数中的元素，可排除
if (nums1[i - 1] > nums2[j - 1])
return findKth(nums1, vector<int>(nums2.begin() + j, nums2.end()), k - j); //nums2的前j个数一定在k之前，所以在剩下的数中找第k - j大的数
else
return findKth(vector<int>(nums1.begin() + i, nums1.end()), nums2, k - i);
//return 0;
}
};
方法三：设l = nums.size()可发现如下规律：
- 若l % 2 == 1，数组中位数 = nums[l / 2] = nums[(l - 1) / 2] = （nums[l / 2] + nums[(l - 1) / 2]）/ 2
- 若l % 2 == 0，数组中位数 = （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较短，故中位数一定在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 —— 数组1整体都比中值大，l1 > r2，中值在2中
l1 = (mid1 == 0)? INT_MIN : nums1[(mid1 - 1) / 2]; //第一次割一定在nums1的中位数上
r1 = (mid1 == 2 * len1)? INT_MAX : nums1[mid1 / 2];
//mid2 = 0 —— 数组2整体都比中值大，l2 > r1，中值在1中
l2 = (mid2 == 0)? INT_MIN : nums2[(mid2 - 1) / 2]; //第一次割一定在nums2的中位数上
r2 = (mid2 == 2 * len2)? INT_MAX : nums2[mid2 / 2];
if(l1 > r2) //说明中位数在数组一的更前半部或数组二的更后半部，故减小mid1，增大mid2。说明数组一的后半部不用找了
r = mid1 - 1;
else if(l2 > r1) //说明中位数在数组二的更前半部或数组一的更后半部，故减小mid2，增大mid1。说明数组一的前半部不用找了
l = mid1 + 1;
else //l1 < r2 && l2 < r1，又因为找的是中位数，故两个割分别在两序列中间。说明Max(l1, l2)就是中位数。
break;
}
//当两数组数字总个数为奇数时，割将个数为奇数的那个数组的中位数分为两个，故max(l1, l2) = min(r1, r2)
return (max(l1, l2)+ min(r1, r2))/2.0;
}
};
