[leetcode]分治算法之Median of Two Sorted Arrays

分治算法之Median of Two Sorted Arrays

• 題幹
• 思想歸類
• 代碼

題幹

leetcode入口

思想歸類

中位數的計算：

假設第一個集合大小為size1，第二個為size2,

那麼中位數可以是第

(size1+size2+1)/2

和

(size1+size2+2)/2

這兩個位置的值

利用分治法，求這兩個位置的值。

二分法：

求兩個有序數組中第K小的數組，對K進行二分

查找到nums1和nums2中第K/2大的數，淘汰掉較小的一個數組的K/2個數組(通過移動下标來實作)

如果數組大小小于K/2，那麼淘汰掉另一個數組的K/2個數

代碼

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int size1=nums1.size();
        int size2=nums2.size();
        
        //如果nums1和nums2的總數是奇數，那麼下面這兩個相等，否則不相等
        int left = (size1+size2+1)/2; //左邊的數位置
        int right= (size1+size2+2)/2; //右邊的數位置
        
        //此題變成了尋找兩個有序數組中第K大的問題
        return ((double)divide_and_conquer(nums1,0,nums2,0,left)+divide_and_conquer(nums1,0,nums2,0,right))/2.0;
        
    }
    
    //i代表nums1的起始位置,j代表nums2的起始位置
    int divide_and_conquer(vector<int>& nums1,int i,vector<int>& nums2,int j,int K){
        //如果起始位置超過各個數組的大小，則在另一個數組中找
        if(i>=nums1.size()) return nums2[j+K-1];
        if(j>=nums2.size()) return nums1[i+K-1];
        if (K == 1) return min(nums1[i], nums2[j]);
		
		//分别找到第K/2個數字進行比較
        int mid1=((i+K/2-1)<nums1.size())?nums1[i+K/2-1]:INT_MAX;
        int mid2=((j+K/2-1)<nums2.size())?nums2[j+K/2-1]:INT_MAX;
        
        //如果淘汰較小數組的前K/2個
        if(mid1<mid2){
            return divide_and_conquer(nums1,i+K/2,nums2,j,K-K/2);
        }
        else{
            return divide_and_conquer(nums1,i,nums2,j+K/2,K-K/2);
        }
        
        
    }
    
};