尋找兩個有序陣列的中位數-有解無憂

該題目如果使用時間復雜度為O（m+n）的演算法則會非常簡單，今天我們在這里介紹一個時間復雜度為O（log(m+n)）的演算法，

我們這里采用二分法的思想去解決這道題目，首先我們給出的陣列是兩個有序陣列，這樣的話，我們可以很方便的將兩個陣列各自分為兩個部分，而我們要尋找的中位數只需要將兩個陣列合并后的陣列分為等長兩部分，并且左邊的最大值小于右邊的最小值即可，那么我們可以先滿足第一個條件，再去尋找滿足第二個條件的 將兩個陣列各自分為兩個部分 的分割方式，找到之后，我們便可以輕而易舉的給出中位數的數值，程式代碼如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2);
int main()
{
    int len_1, len_2;
    cin >> len_1 >> len_2;
    vector<int> nums1(len_1);
    vector<int> nums2(len_2);
    for (int i = 0; i < len_1; ++i)
    {
        cin >> nums1[i];
    }
    for (int i = 0; i < len_2; ++i)
    {
        cin >> nums2[i];
    }
    cout << findMedianSortedArrays(nums1, nums2);
    return 0;
}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
{
    int m = nums1.size();
    int n = nums2.size();
    vector<int> temps1;
    vector<int> temps2;
    if (m > n)
    {
        temps1 = nums2;
        temps2 = nums1;
        int tmp = m; m = n; n = tmp;
    }
    else
    {
        temps1 = nums1;
        temps2 = nums2;
    }
    int iMin = 0, iMax = m, halflen = (m + n + 1) / 2;
    //以上步驟保證陣列1短于陣列2，這樣陣列1中的任意一種分法在陣列2中都成立，
    while (iMin <= iMax)
    {
        int i = (iMin + iMax) / 2;
        int j = halflen - i;//因為m<=n,所以j可以直接賦值成halflen - i
        if (i < iMax && temps2[j - 1] > temps1[i]) 
        {
            iMin = i + 1; // i is too small
        }
        else if (i > iMin && temps1[i - 1] > temps2[j]) 
        {
            iMax = i - 1; // i is too big
        }
        //以上步驟是是實作二分法的關鍵代碼，每次二分尋找合適的i值，
        else 
        { // i is perfect
            double maxLeft = 0;

            if (i == 0) 
            { 
                maxLeft = temps2[j - 1]; 
                //nums1左邊部分沒有元素，因此左邊最大的是nums2的左邊部分的最后一個元素
            }
            else if (j == 0) 
            { 
                maxLeft = temps1[i - 1]; 
                //nums2左邊部分沒有元素，因此左邊最大的是nums1的左邊部分的最后一個元素
            }
            else 
            { 
                maxLeft = max(temps1[i - 1], temps2[j - 1]); 
                //nums1左邊部分和nums2左邊部分都有元素，取最大值
            }
            if ((m + n) % 2 == 1) 
            { 
                return maxLeft; 
                //如果是奇數就直接回傳該值
            }

            double minRight = 0;

            if (i == m) 
            { 
                minRight = temps2[j]; 
            }
            else if (j == n) 
            { 
                minRight = temps1[i]; 
            }
            else 
            { 
                minRight = min(temps2[j], temps1[i]); 
            }

            return (maxLeft + minRight) / 2;
            //如果是偶數就取兩個數加和除以2
        }
    }
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40783.html

標籤：C++

上一篇：圓桌均分硬幣 ——（推導式子）

下一篇：WDK驅動除錯問題點滴