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
原题：https://leetcode.com/PRoblems/median-of-two-sorted-arrays/?tab=Description
分析：通常情况下我们要求得一系列数中的中位数，应该都是要知道所有的数之后才能决定中位数的具体值，也就是具有O(n)以上的复杂度。但是，假如说知道了给定的一系列数的大小关系（即已经有序排列好），则我们可以直接根据这一系列数的个数直接判断。比如总个数为n，当n为奇数时，中位数应该在n / 2处；当n为偶数时，中位数应该为n / 2 - 1与n / 2的平均值。此处数列的取值范围是[ 0, n )。 上题中给定的条件是两个已有序的数组（题意应该是默认从小到大排列）。最简单直接的方法是通过一个merge过程将两列数合并为一列数，再用上述的O(1)的方法直接得到结果，这样总过程是O(n)的复杂度。但是题目要求的是O(log(m+n））的复杂度。 不妨设两组数为A[n]、B[m]，且n <= m。解决方法是始终取定一组数，个数为k = （n + m - 1） / 2 + 2 。这样，在这一组数中一定包含了中位数或者取得中位数的必要信息，且都是在这k个数的“边缘”取得。假如这k个数取A[]、B[]中较小的一部分，则“边缘数”为k个数范围内最大的第一个、第二个和第三个。一般情况下，这k个数必须在A[]、B[]中同时取得，设在A[]中最大的数为A[midA]、在B[]中最大的数为B[midB]。 以下是一种经检验证明可行的算法：
public double findMedianSortedArrays(int A[], int B[]) { int n = A.length; int m = B.length; // the following call is to make sure len(A) <= len(B). // yes, it calls itself, but at most once, shouldn't be // consider a recursive solution if (n > m) return findMedianSortedArrays(B, A); // now, do binary search int k = (n + m - 1) / 2; int l = 0, r = Math.min(k, n); // r is n, NOT n-1, this is important!! while (l < r) { int midA = (l + r) / 2; int midB = k - midA; if (A[midA] < B[midB]) l = midA + 1; else r = midA; } // after binary search, we almost get the median because it must be between // these 4 numbers: A[l-1], A[l], B[k-l], and B[k-l+1] // if (n+m) is odd, the median is the larger one between A[l-1] and B[k-l]. // and there are some corner cases we need to take care of. int a = Math.max(l > 0 ? A[l - 1] : Integer.MIN_VALUE, k - l >= 0 ? B[k - l] : Integer.MIN_VALUE); if (((n + m) & 1) == 1) return (double) a; // if (n+m) is even, the median can be calculated by // median = (max(A[l-1], B[k-l]) + min(A[l], B[k-l+1]) / 2.0 // also, there are some corner cases to take care of. int b = Math.min(l < n ? A[l] : Integer.MAX_VALUE, k - l + 1 < m ? B[k - l + 1] : Integer.MAX_VALUE); return (a + b) / 2.0;}注：该算法引用自：https://leetcode.com/problems/median-of-two-sorted-arrays/?tab=Solutions ( 4.Share my iterative solution) with O(log(min(n, m)))
以下是我根据算法伪代码写的C++代码，基本上与伪代码差不多。
#include <climits>using namespace std;class Solution {public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { if (nums1.size() == 0) { if (nums2.size() % 2 == 0) { return double(nums2[nums2.size() / 2 - 1] + nums2[nums2.size() / 2]) / 2.0; } else { return double(nums2[nums2.size() / 2]); } } else if (nums2.size() == 0) { if (nums1.size() % 2 == 0) { return double(nums1[nums1.size() / 2 - 1] + nums1[nums1.size() / 2]) / 2.0; } else { return double(nums1[nums1.size() / 2]); } } int n = nums1.size(), m = nums2.size(); if (n > m) return findMedianSortedArrays(nums2, nums1); int k = (n + m - 1) / 2; int l = 0, r = min(k, n); while (l < r) { int midA = (l + r) / 2; int midB = k - midA; if (nums1[midA] < nums2[midB]) l = midA + 1; else r = midA; } int a = max(l > 0 ? nums1[l - 1] : INT_MIN, k - l >= 0 ? nums2[k - l] : INT_MIN); if ((n + m) % 2 == 1) { return double(a); } else { int b = min(l < n ? nums1[l] : INT_MAX, k - l + 1 < m ? nums2[k - l + 1] : INT_MAX); return double(a + b) / 2.0; } } int max(int a, int b) { if (a > b) return a; else return b; } int min(int a, int b) { if (a < b) return a; else return b; }};新闻热点
疑难解答
