題解

劃分元素組

長數組a,短數組b

數組元素組1元素組2

a(長度為m)	a1,a2,a3…ai	ai+1,ai+2…am-1,am
b(長度為n)	b1,b2,b3…bj	bj+1,bj+2…bn-1,bn

劃分保證元素組1中元素一定小于等于元素組2中的元素，且size(元素組1)-size(元素組2)的絕對值最小。

若m+n為偶數，劃分之后size(元素組1)==size(元素組2)。則中位數一定是a_i,a_i+1,b_j,b_j+1這四個數中兩個數的平均數。

若m+n為奇數，劃分之后size(元素組1)+1==size(元素組2)。則中位數一定是a_i,a_i+1,b_j,b_j+1這四個數中的一個。

如何劃分數組

劃分長數組，因為長數組中的元素能定位短數組中的不同元素（也可能定位不到），而短數組定位長數組中的元素是受限的。

根據長數組元素定位短數組元素。
考慮如下情況。
短數組a = {3};
長數組b = {1,2,4,5,6};
若用短數組去定位長數組，則a₀總是定位到b₃(下標=(m+n)/2-0=3，采用不同的計算方法可以得到不同的下標),而b₃=5，顯然不是中位數。

確定中位數的值

若m+n為偶數，則ans = (max(a_i,b_j)+min(a_i+1,b_j+1))/2;

若m+n為奇數，由于元素組2比元素組1個數多一個，中位數一定存在于a_i+1,b_j+1，則ans = min(a_i+1,b_j+1);

Code

class Solution { public:double findMedianSortedArrays(vector<int>& a, vector<int>& b) {// m,n表示兩vector數組的大小。int m = a.size();int n = b.size();// 若a數組長度小于b數組，則交換兩數組。因為我們要根據長數組元素定位短數組中的對應元素if(m < n) return findMedianSortedArrays(b,a);int l = 0, r = m;double ans;int mid1, mid2,left1,left2,right1,right2;while (l < r) {// mid1為二分數組a,mid2對應mid1取值mid1 = (l + r) / 2;mid2 = (m + n) / 2 - mid1;// 如果mid2越界，調整l和r，重新確定mid1。if(mid2 < 0){r = mid1;continue;}if(mid2 > n){l = mid1+1;continue;}// 取出a[i]、a[i+1]、b[j]、b[j+1]。左邊越界，設為最小值；右邊越界，設為最大值。left1 = mid1 - 1 <= -1 ? INT_MIN : a[mid1 - 1];right1 = mid1 >= m ? INT_MAX : a[mid1];left2 = mid2 - 1 <= -1 ? INT_MIN : b[mid2 - 1];right2 = mid2 >= n ? INT_MAX : b[mid2];// 如果滿足左邊元素組小于等于右邊元素組，跳出循環if (right1 >= left2 && left1 <= right2) {break;}// 如果不滿足，則調整l,r重新取mid1。if (right1 < left2) {l = mid1+1;}if (left1 > right2) {r = mid1;}}//如果為奇數if (1 & (m + n)) {ans = 1.0*min(right1, right2);}else {ans = 1.0*(max(left1, left2) + min(right1, right2)) / 2;}return ans;} };

總結

以上是生活随笔為你收集整理的LeetCode4. Median of Two Sorted Arrays(二分法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。