题目：Median of Two Sorted Arrays https://leetcode.com/PRoblems/median-of-two-sorted-arrays/?tab=Description
问题描述： 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)).
首先这里给出了两个有序的数组A[m], B[n]，其长度分别为m，n。我们可以设定m>n。下面给出O(log n)的算法思路。
首先我们可以先处理某些特殊情况： 1. 当m，n其中一个为0时，直接求另外一个数组的中位数； 2. 当m，n都为偶数，其中位数分别是A[m/2 -1]和A[m/2]，B[n/2 -1]和B[n/2]的平均值。当（1）A[m/2 -1] <= B[n/2 -1], A[m/2] >= B[n/2], 直接返回数组B的平均数。（2）A[m/2 -1] >= B[n/2 -1], A[m/2] <= B[n/2]，直接返回数组A的平均数。 （1）如果medA <= medB, 那么我们可以去掉数组B中后 n/2 （取整）个元素，得到新的数组B’，同时去掉数组A中前n/2个元素，得到新的数组A’。 （2）如果medA > medB, 那么我们可以去掉数组B中前 n/2 （取整）个元素，得到新的数组B’，同时去掉数组A中后n/2个元素，得到新的数组A’。 我们可以证明这样得到新的数组A’，B’ 的中位数与数组A，B的中位数是一样的。这样子就得到了一个递归的求中位数的算法。直到其中数组B的长度为1，我们可以直接找出中位数。这种算法的复杂度为O(log n)。
实现代码：
#include<iostream>#include<vector>using namespace std;double MedianofanArray(vector<int>& nums){ int length = nums.size(); if (length % 2) return nums[length / 2]; else { double p = nums[length / 2 - 1] + nums[length / 2]; return p / 2; }}double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2){ int m = nums1.size(), n = nums2.size(); if (m == 0) return MedianofanArray(nums2); else if (n == 0) return MedianofanArray(nums1); //ensure that m >= n else if (m < n) { return findMedianSortedArrays(nums2, nums1); } else { double med1 = MedianofanArray(nums1), med2 = MedianofanArray(nums2); if (med1 == med2) return med1; else if ( (n % 2 != 1 && m % 2 != 1 && nums2[n / 2 - 1] >= nums1[m / 2 - 1] && nums2[n / 2] <= nums1[m / 2]) || (n % 2 == 1 && m % 2 != 1 && nums2[n / 2] >= nums1[m / 2 - 1] && nums2[n / 2] <= nums1[m / 2]) ) return med2; else if ( (n % 2 != 1 && m % 2 != 1 && nums2[n / 2 - 1] <= nums1[m / 2 - 1] && nums2[n / 2] >= nums1[m / 2]) || (n % 2 != 1 && m % 2 == 1 && nums1[m / 2] >= nums2[n / 2 - 1] && nums1[m / 2] <= nums1[n / 2]) ) return med1; else if (m == 1) return (med1 + med2) / 2; else if (n == 1) { if (m % 2) { if (med2 <= med1) { if(med2 <= nums1[m / 2 - 1]) return (med1 + nums1[m / 2 - 1]) / 2; else return (med1 + med2) / 2; } else { if(med2 >= nums1[m / 2 + 1]) return (med1 + nums1[m / 2 + 1]) / 2; else return (med1 + med2) / 2; } } else { if (med2 <= nums1[m / 2 - 1]) return nums1[m / 2 - 1]; else if (med2 >= nums1[m / 2]) return nums1[m / 2]; else return med2; } } else { vector<int>::iterator begin1 = nums1.begin(), begin2 = nums2.begin(), end1 = nums1.end(), end2 = nums2.end(); if (med1 < med2) { nums1.erase(begin1, begin1 + (int)(n / 2)); nums2.erase(end2 - (int)(n / 2), end2); } else { nums2.erase(begin2, begin2 + (int)(n / 2)); nums1.erase(end1 - (int)(n / 2), end1); } return findMedianSortedArrays(nums1, nums2); } }}int main() //test{ vector<int> nums1, nums2; nums1.push_back(1); nums1.push_back(2); nums1.push_back(6); nums1.push_back(7); nums2.push_back(3); nums2.push_back(4); nums2.push_back(5); nums2.push_back(8); for (int i = 0; i < nums1.size(); ++i) { cout << nums1[i]<<' '; } cout << endl; for (int i = 0; i < nums2.size(); ++i) { cout << nums2[i] << ' '; } cout << endl; double medoftowArray = findMedianSortedArrays(nums1, nums2); cout << medoftowArray << endl; system("pause");}新闻热点
疑难解答
