題目：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");}新聞熱點
疑難解答
