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
分析：通常情況下我們要求得一系列數(shù)中的中位數(shù)，應(yīng)該都是要知道所有的數(shù)之后才能決定中位數(shù)的具體值，也就是具有O(n)以上的復(fù)雜度。但是，假如說知道了給定的一系列數(shù)的大小關(guān)系（即已經(jīng)有序排列好），則我們可以直接根據(jù)這一系列數(shù)的個數(shù)直接判斷。比如總個數(shù)為n，當(dāng)n為奇數(shù)時，中位數(shù)應(yīng)該在n / 2處；當(dāng)n為偶數(shù)時，中位數(shù)應(yīng)該為n / 2 - 1與n / 2的平均值。此處數(shù)列的取值范圍是[ 0, n )。 上題中給定的條件是兩個已有序的數(shù)組（題意應(yīng)該是默認從小到大排列）。最簡單直接的方法是通過一個merge過程將兩列數(shù)合并為一列數(shù)，再用上述的O(1)的方法直接得到結(jié)果，這樣總過程是O(n)的復(fù)雜度。但是題目要求的是O(log(m+n））的復(fù)雜度。 不妨設(shè)兩組數(shù)為A[n]、B[m]，且n <= m。解決方法是始終取定一組數(shù)，個數(shù)為k = （n + m - 1） / 2 + 2 。這樣，在這一組數(shù)中一定包含了中位數(shù)或者取得中位數(shù)的必要信息，且都是在這k個數(shù)的“邊緣”取得。假如這k個數(shù)取A[]、B[]中較小的一部分，則“邊緣數(shù)”為k個數(shù)范圍內(nèi)最大的第一個、第二個和第三個。一般情況下，這k個數(shù)必須在A[]、B[]中同時取得，設(shè)在A[]中最大的數(shù)為A[midA]、在B[]中最大的數(shù)為B[midB]。 以下是一種經(jīng)檢驗證明可行的算法：
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)))
以下是我根據(jù)算法偽代碼寫的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; }};新聞熱點
疑難解答
