程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode題解||Median of Two Sorted Arrays問題

leetcode題解||Median of Two Sorted Arrays問題

編輯:C++入門知識

leetcode題解||Median of Two Sorted Arrays問題


problem:

 

There are two sorted arrays A and B 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)).

thinking:

 

(1)求中位數,就是求已序數列的中間位置對應的數字,分奇偶。兩個已序數組求中位數,就是求合並後的中位數。

(2)采用merge sort合並排序的方法求中位數,很直觀,但時間復雜度為O(m+n),不符合本題要求。

(3)采用分治的策略,時間復雜度滿足O(m+n)。

參考:http://blog.csdn.net/zxzxy1988/article/details/8587244

 

該方法的核心是將原問題轉變成一個尋找第k小數的問題(假設兩個原序列升序排列),這樣中位數實際上是第(m+n)/2小的數。所以只要解決了第k小數的問題,原問題也得以解決。

首先假設數組A和B的元素個數都大於k/2,我們比較A[k/2-1]和B[k/2-1]兩個元素,這兩個元素分別表示A的第k/2小的元素和B的第k/2小的元素。這兩個元素比較共有三種情況:>、<和=。如果A[k/2-1]B[k/2-1]時存在類似的結論。

當A[k/2-1]=B[k/2-1]時,我們已經找到了第k小的數,也即這個相等的元素,我們將其記為m。由於在A和B中分別有k/2-1個元素小於m,所以m即是第k小的數。(這裡可能有人會有疑問,如果k為奇數,則m不是中位數。這裡是進行了理想化考慮,在實際代碼中略有不同,是先求k/2,然後利用k-k/2獲得另一個數。)

通過上面的分析,我們即可以采用遞歸的方式實現尋找第k小的數。此外我們還需要考慮幾個邊界條件:

如果A或者B為空,則直接返回B[k-1]或者A[k-1];
如果k為1,我們只需要返回A[0]和B[0]中的較小值;
如果A[k/2-1]=B[k/2-1],返回其中一個;

code:

 

分治策略尋找第K、k-pa、k-pb....大的數字,邊界條件確定遞歸調用返回有效解。

 

double findKth(int a[], int m, int b[], int n, int k)  
{  
    //always assume that m is equal or smaller than n  
    if (m > n)  
        return findKth(b, n, a, m, k);  
    if (m == 0)  
        return b[k - 1];  
    if (k == 1)  
        return min(a[0], b[0]);  
    //divide k into two parts  
    int pa = min(k / 2, m), pb = k - pa;  
    if (a[pa - 1] < b[pb - 1])  
        return findKth(a + pa, m - pa, b, n, k - pa);  
    else if (a[pa - 1] > b[pb - 1])  
        return findKth(a, m, b + pb, n - pb, k - pb);  
    else  
        return a[pa - 1];  
}  
  
class Solution  
{  
public:  
    double findMedianSortedArrays(int A[], int m, int B[], int n)  
    {  
        int total = m + n;  
        if (total & 0x1)  
            return findKth(A, m, B, n, total / 2 + 1);  
        else  
            return (findKth(A, m, B, n, total / 2)  
                    + findKth(A, m, B, n, total / 2 + 1)) / 2;  
    }  
};  

分治遞歸算法簡潔清楚,邊界條件完備,時間復雜度為O(log(m+n))

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved