天天看點
傳回

【力扣LeetCode】4 尋找兩個有序數組的中位數

題目描述（難度難）

給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2。

請你找出這兩個有序數組的中位數，并且要求算法的時間複雜度為 O(log(m + n))。

你可以假設 nums1 和 nums2 不會同時為空。

示例 1:

nums1 = [1, 3]

nums2 = [2]

則中位數是 2.0

示例 2:

nums1 = [1, 2]

nums2 = [3, 4]

則中位數是 (2 + 3)/2 = 2.5

連結

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

思路

題目要求時間複雜度為：O(log(m + n))。顯然，需要采用二分的方案。

通過分析，我們要得到的是中位數，中位數即是左邊和右邊個數相同，而我們是知道兩個數組的總個數的，是以，對一個數組進行二分查找，一個數組的一個切分點确定時，第二個數組的切分店也随之确定。這樣的複雜度為O(log(min(m，n)))。具體實作時，要特别注意，當查找到兩端點時怎麼操作，因為完全有可能一個數組全部的資料都在中位數的左邊或者右邊。

正确詳細思路參考（具體解法不推薦）：

https://blog.csdn.net/hk2291976/article/details/51107778

這種思路是錯誤的（漏掉了很多情況）：

https://www.cnblogs.com/TenosDoIt/p/3554479.html

具體分析如下：

nums1 和 A 均表示第一個數組

nums2 和 B 均表示第二個數組

二分查找

首先确定子問題。根據中位數的定義，中位數的左右兩側數字個數相同，且其左邊的數字比其小，右邊的數字比其大。構造兩個子集，分别是左右子集，假定取

nums1

中的前

i (i ∈[0, m])

個放在左子集，

nums2

的前

j (j ∈[0, n])

個放在左子集，此時左子集數字個數為

i + j

，右子集數字個數為

m + n - i - j

。關系是：

【力扣LeetCode】4 尋找兩個有序數組的中位數

假設我們周遊

i

，偶數時為

j = (m + n) / 2 - i

，奇數時為

j = (m + n + 1) / 2 - i

，但如果

m > n

，

j

會為負數，是以要求

m <= n

。其實偶數時

j

表示成奇數時的式子也是可以的，因為C語言裡邊的除法是整除，是以加上

1

不會影響

j

的結果。是以

j = (m + n + 1) / 2 - i

且

m <= n

。

另一個要求是：

A[i - 1] <= B[j]   
    B[j - 1] <= A[i]

令

i = (begin + end) / 2

：

  • 如果

    A[i - 1] > B[j]

     ，則說明需要減小

    i

     ，減小

    i

     的同時

    j

     也會增大，這樣

    A[i - 1]

     的值就會減小，

    B[j]

     的值會增大，向着滿足條件的方向靠近。而且因為從

    i

     到

    end

     之間

    A

     是遞增的，是以

    i

     到

    end

     之間的都不符合(

    i

     越大，

    A[i - 1]

     越大，

    B[j]

     越小)，故直接将

    end

     置為

    i - 1

     。
  • 如果

    B[j - 1] > A[i]

     ，則說明需要減小

    j

     ，減小

    j

     的意味着增大

    i

     ，這樣

    A[i]

     的值就會增大，

    B[j + 1]

     的值會減小，向着滿足條件的方向靠近。而且因為從

    begin

     到

    i

     之間

    A

     是遞增的，是以

    begin

     到

    i

     之間的都不符合(

    i

     越小，

    A[i - 1]

     越小，

    B[j]

     越大)，故直接将

    begin

     置為

    i + 1

     。
  • 如果兩個條件都滿足說明已經周遊到正确的中間位置，進行後續邏輯判斷即可。需要注意的是邊界情況，在判斷時一定要保證數組索引在範圍之内，對于不符合的情況，進入到最終的判斷邏輯中進行處理。

代碼 

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    	int len1 = nums1.size();
    	int len2 = nums2.size();
    	if(len1 > len2){
    		return findMedianSortedArrays(nums2, nums1);
    	}
    	int start = 0;
		int end = len1;
		int halfLen = (len1 + len2 + 1) / 2; 
    	while(start <= end){
    		int i = (start + end) / 2;
    		int j = halfLen - i;
    		if(i < end && nums2[j-1] > nums1[i]){
    			start = i + 1;
    		}
    		else if(i > start && nums1[i-1] > nums2[j]){
    			end = i - 1;
    		}
    		else{
    			int maxLeft = 0;
    			if(i == 0){
    				maxLeft = nums2[j-1];
    			}
    			else if(j == 0){
    				maxLeft = nums1[i-1];
    			}
    			else{
    				maxLeft = nums1[i-1] > nums2[j-1] ? nums1[i-1] : nums2[j-1];
    			}
    			if((len1 + len2) % 2 == 1){
    				return maxLeft;
    			}
    			
    			int minRight = 0;
    			if(i == len1){
    				minRight = nums2[j];
    			}
    			else if(j == len2){
    				minRight = nums1[i];
    			}
    			else{
    				minRight = nums1[i] < nums2[j] ? nums1[i] : nums2[j];
    			}
    			return (maxLeft + minRight) / 2.0;
    		}
    	}
    	return 0;
	}
};

錯誤的思路寫得很難受的代碼，不想扔放上來檢討自己

class SolutionError {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    	if(nums1.size() == 0){
    		return nums2.size() % 2 ? nums2[nums2.size()/2] : (nums2[nums2.size()/2-1] + nums2[nums2.size()/2]) / 2.0;
    	}
    	if(nums2.size() == 0){
    		return nums1.size() % 2 ? nums1[nums1.size()/2] : (nums1[nums1.size()/2-1] + nums1[nums1.size()/2]) / 2.0;
    	}
        if(nums1.size() == 1 && nums2.size() == 1){  // 遞歸結束條件
        	return (nums1[0] + nums2[0]) / 2.0;
        }
        if(nums1.size() == 1){
        	int index = nums2.size() / 2;
			if(nums2.size() % 2 == 0){
				if(nums1[0] >= nums2[index]){
					return nums2[index];
				}
				else if(nums1[0] <= nums2[index-1]){
					return nums2[index-1];
				}
				else{
					return nums1[0];
				}
			}
			else{
				if(nums1[0] >= nums2[index-1] && nums1[0] <= nums2[index+1]){
					return (nums1[0] + nums2[index]) / 2.0;
				}
				else if(nums1[0] < nums2[index-1]){
					return (nums2[index-1] + nums2[index]) / 2.0;
				}
				else{
					return (nums2[index] + nums2[index+1]) / 2.0;
				}
			}
        }
        if(nums2.size() == 1){
        	int index = nums1.size() / 2;
			if(nums1.size() % 2 == 0){
				if(nums2[0] >= nums1[index]){
					return nums1[index];
				}
				else if(nums2[0] <= nums1[index-1]){
					return nums1[index-1];
				}
				else{
					return nums2[0];
				}
			}
			else{
				if(nums2[0] >= nums1[index-1] && nums2[0] <= nums1[index+1]){
					return (nums2[0] + nums1[index]) / 2.0;
				}
				else if(nums2[0] < nums1[index-1]){
					return (nums1[index-1] + nums1[index]) / 2.0;
				}
				else{
					return (nums1[index] + nums1[index+1]) / 2.0;
				}
			}
        }
        double median1 = nums1.size() % 2 ? nums1[nums1.size()/2] : (nums1[nums1.size()/2-1] + nums1[nums1.size()/2]) / 2.0;
        double median2 = nums2.size() % 2 ? nums2[nums2.size()/2] : (nums2[nums2.size()/2-1] + nums2[nums2.size()/2]) / 2.0;
        if(median1 == median2){
        	return median1;
        }
        else if(median1 > median2){
        	int cutlen = nums1.size() < nums2.size() ? nums1.size()/2 : nums2.size()/2;
        	for(int i = 0; i < cutlen; i++){
        		nums1.erase(nums1.begin());
        		nums2.pop_back();
        	}
        	return findMedianSortedArrays(nums1, nums2);
        }
        else{
        	int cutlen = nums1.size() < nums2.size() ? nums1.size()/2 : nums2.size()/2;
        	for(int i = 0; i < cutlen; i++){
        		nums1.pop_back();
        		nums2.erase(nums2.begin());
        	}
        	return findMedianSortedArrays(nums1, nums2);
        }
    }
};
leetcode 中位數 兩個有序數組
上一篇: Leetcode初學——尋找兩個有序數組的中位數
下一篇: LeetCode——尋找兩個有序數組的中位數

繼續閱讀