本文目錄

??題意分析

??解題思路：

1、直接法? （?）

2、歸并思想?（?）

①《LeetCode》第88題——合并兩個有序數(shù)組

3、二分查找（??）

整體思想：

題目如下 ：??

給定兩個大小分別為 m 和 n 的正序（從小到大）數(shù)組?nums1 和?nums2。請你找出并返回這兩個正序數(shù)組的 中位數(shù) 。

算法的時間復(fù)雜度應(yīng)該為 O(log (m+n))?

示例 1：

輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合并數(shù)組 = [1,2,3] ，中位數(shù) 2

示例 2：

輸入：nums1 = [1,2], nums2 = [3,4]
輸出：2.50000
解釋：合并數(shù)組 = [1,2,3,4] ，中位數(shù) (2 + 3) / 2 = 2.5

??題意分析

首先，我們需要注意的一點就是關(guān)于本題時間復(fù)雜度的要求，本題要求的時間復(fù)雜度為? O(log (m+n)) ，這里一定要特別注意！！

其次，我們來對給出的示例給出解釋說明，分析題意：

1. 首先對于示例一，題目給出了兩個數(shù)組——nums1和nums2，兩個數(shù)組的的合并之后且排好序之后為 【1 2 3】，又因為是 double型 輸出，此時它的中位數(shù)就是 【2.00000】；
2. 其次對于示例二，題目給出了兩個數(shù)組，數(shù)組中的元素分別為【1 2】和【3 4】，此時經(jīng)過排序，我們得到【1 2 3 4】這樣的數(shù)組，此時數(shù)組的長度為偶數(shù)，因此中位數(shù)的計算就是【(2 + 3) / 2 = 2.5】

??解題思路：

1、直接法? （?）

首先，大家拿道題，第一種想到的可能就是直接對這兩個數(shù)組進行合并在進行排序處理，排完序之后緊接著根據(jù)數(shù)據(jù)長度的奇偶性，我們來判斷中位數(shù)的到底是n/2還是n/2+1:

代碼如下：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
 vector<int>arr;

    for(auto& e :nums1) {arr.push_back(e);}
    for(auto& e :nums2) {arr.push_back(e);}
    sort(arr.begin(),arr.end());

    int m=arr.size();
    if( m % 2 == 0){
     return (double)(arr[m/2]+arr[m/2-1]) /2.0;
    } else{
    return arr[m/2];
    }
  }
};

???? 這種做法可以通過但是卻不符合提本題的要求，因為它的時間復(fù)雜度就為了?O((m+n)log (m+n))，這樣做時間復(fù)雜度就取決于排序的代價。因此，這種方法我就此忽略。

2、歸并思想?（?）

其實我們在稍加思考，就可以想到一種優(yōu)化方法。

???? 我們可以聯(lián)想到歸并排序，這個我想大概應(yīng)該都學過的。我們不用在進行先合并在sorted，我們可以直接把這兩個歸并為一個已經(jīng)排序好的數(shù)組。此時這就是雙指針的算法，時間復(fù)雜度此時為O(m+n)。

這個還可以進行優(yōu)化，我們不需要對全部進行歸并操作，因為我們只關(guān)心中位數(shù)，因此我們可以計算中位數(shù)的下標，假設(shè)此時中位數(shù)的下表為?k，時間復(fù)雜度就為O(k)，k的取值取決于數(shù)組的長度還是，介于（m+n）/2和?（m+n）/2+1。但是此時依然也不能滿足我們題意的 log 級別的時間復(fù)雜度的要求.
?

①《LeetCode》第88題——合并兩個有序數(shù)組

注意：

• 如果大家對這個排序還不熟悉的小伙伴，我在這里就連帶還給出了以下題目的講解，幫助大家認識 歸并排序 思想 ：
• 《LeetCode》第88題——合并兩個有序數(shù)組??

題目如下：

給你兩個按 非遞減順序 排列的整數(shù)數(shù)組?nums1 和 nums2，另有兩個整數(shù) m 和 n ，分別表示 nums1 和 nums2 中的元素數(shù)目。

請你 合并 nums2 到 nums1 中，使合并后的數(shù)組同樣按 非遞減順序 排列。

注意：

• 最終，合并后數(shù)組不應(yīng)由函數(shù)返回，而是存儲在數(shù)組 nums1 中。為了應(yīng)對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應(yīng)合并的元素，后 n 個元素為 0 ，應(yīng)忽略。nums2 的長度為 n 。

示例 1：

輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
解釋：需要合并 [1,2,3] 和 [2,5,6] 。
合并結(jié)果是 [1,2,2,3,5,6] ，其中斜體加粗標注的為 nums1 中的元素。

示例 2：

輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
解釋：需要合并 [1] 和 [] 。
合并結(jié)果是 [1] 。

示例 3：

輸入：nums1 = [0], m = 0, nums2 = [1], n = 1
輸出：[1]
解釋：需要合并的數(shù)組是 [] 和 [1] 。
合并結(jié)果是 [1] 。
注意，因為 m = 0 ，所以 nums1 中沒有元素。nums1 中僅存的 0 僅僅是為了確保合并結(jié)果可以順利存放到 nums1 中。

??題意分析：

1. 首先，根據(jù)題意，我們可以知道給出了的數(shù)據(jù)都是已經(jīng)排好序的了，因此，這就減少了我們的一步操作；
2. 緊接著我們可以發(fā)現(xiàn)最終是由nums1返回，因此它的空間都足夠大

??解題思路：

1、直接法

• 最容易想到的辦法無疑是把數(shù)組?nums2? 的數(shù)據(jù)元素全部放入到數(shù)組?nums1 的尾部，因此題意告訴我們 nums1 的空間大小為【m+n】，然后直接對整個數(shù)組進行排序即可。

代碼如下：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
           //此時我們選nums1作為 填充數(shù)組，把nums2中元素全部插入到nums1中
            for(int i=0; i<n; ++i) 
            {
                nums1[m+i]=nums2[i];
            }
            //此時，全部的元素都在nums1數(shù)組中了，最后排序輸出即可
            sort(nums1.begin(),nums1.end());
 }
};

性能分析：

• 時間復(fù)雜度：跟我們上述暴力解《尋找兩個正序數(shù)組的中位數(shù)》一樣，此時 時間復(fù)雜度為O((m+n)log(m+n))
• 空間復(fù)雜度：因為初始時nums1 的空間長度大小已經(jīng)為 （m+n）了。因此無需在開辟額外的空間對其進行存放操作，因此 空間復(fù)雜度為O(1)

2、歸并排序思想

• 如果我們仔細觀察這到題很明顯就是需要利用 二路歸并排序?的思想來做。先確定排序后數(shù)組的長度，緊接著比較兩數(shù)組最后的元素的大小，大的放入新數(shù)組的最后一位。（因為本題 nums1 數(shù)組的長度是 （m+n），所以我們直接覆蓋到 nums1 數(shù)組之后即可）

圖解：

• 開始時如下圖所示：

• ?第一步，比較 3和6 的大小，此時 6比3 大，因此，把6插入到末尾，同時 l2和tail 兩個指針同時往前移動一個位置

• ?第二步：此時在比較 3和5 的大小，發(fā)現(xiàn)5比3大，因此同上述操作一樣，把 5 插入到 tail指向的位置，同時兩個指針在往前移動一位

?

• 第三步：此時比較 3和2 的大小，發(fā)現(xiàn)此時 3比2 大，因此，把3插入到 tail指向的位置，同時? tail和 l1 在往前移動一位

• ?第四步：緊接著再次比較 2和2 的大小，發(fā)現(xiàn)此時一樣大，隨便取 l1和l2 位置對應(yīng)的元素插入到 tail處即可，我們這里是把 l2位置處的 插入到 tail 處。同時移動 l2和tail?

?

• 第五步：此時 nums2的數(shù)據(jù) 已經(jīng)處理完畢了，nums1 中還有數(shù)據(jù)，只需把 nums1 剩余的元素 放入 tail 所指的位置即可，最后完成排序。

代碼如下：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int l1 = m - 1;
        int l2 = n - 1;
        int tail = m + n - 1;
        while (l1 >= 0 && l2 >= 0)
        {
            if (nums1[l1] > nums2[l2])
            {
                nums1[tail--] = nums1[l1--];
            }
            else
            {
                nums1[tail--] = nums2[l2--];
            }
        }
        while (l1 >= 0)
        {
            nums1[tail--] = nums1[l1--];
        }
        while (l2 >= 0)
        {
            nums1[tail--] = nums2[l2--];
        }
    }
};

性能分析：

• 時間復(fù)雜度：指針移動單調(diào)遞減，最多移動?m+n 次，因此 時間復(fù)雜度為?O(m+n)。
• 空間復(fù)雜度：直接對數(shù)組?nums1 原地修改，不需要額外空間，因此 空間復(fù)雜度為O(1)。

溫馨小提示：

我們除了從后往前操作之外，還有從前往后操作。這個任務(wù)就交給大家了，原理跟上面講到的一樣的?。?！

3、二分查找（??）

最后，其實我們可以想到，要想實現(xiàn) log 級別的時間復(fù)雜度，最容易想到的就是采用二分查找的思想。
但是二分查找，我們之前學過的都是對一個數(shù)組進行二分查找，本題我們這里有兩個數(shù)組，因此此題的難度我們可以看到標的是 困難。但是也不要害怕，接下來我?guī)Т蠹曳治鲆徊?br> ?

整體思想：

• 更有效的方法是使用二叉搜索，我們可以在兩個數(shù)組中找到分區(qū)點，使得分區(qū)點左側(cè)的元素小于右側(cè)的元素。然后，可以通過取左分區(qū)的最大值和右分區(qū)的最小值來找到中位數(shù)?。?！

圖解：

?

• ?分區(qū)點不滿足的示例：

• 極端情況1：

• ?極端情況2：

?

?

具體步驟：

1. 首先，記錄下兩個數(shù)組的長度大小，以備后序的計算中位數(shù)做準備；
2. 為了防止分區(qū)點的在第二個數(shù)組的兩側(cè)都有元素，導(dǎo)致出現(xiàn)數(shù)組越界的現(xiàn)象。在此實現(xiàn)中，我們首先檢查第一個數(shù)組的長度是否大于第二個數(shù)組的長度。如果是，我們交換數(shù)組以確保第一個數(shù)組始終是較短的那個數(shù)組；
3. 然后，我們使用二叉搜索來查找兩個數(shù)組的分區(qū)點，我們計算分區(qū)點。使得兩個數(shù)組中分區(qū)左側(cè)的元素數(shù)小于分區(qū)右側(cè)的元素數(shù)；
4. 找到較短數(shù)組的分區(qū)點partition1，利用公式找到較長數(shù)組的分區(qū)點partition2;
5. 然后我們檢查分區(qū)點是否在數(shù)組的邊界，如果沒有，我們檢查分區(qū)點處元素是否形成有效的中位數(shù)；?如果沒有，我們可以相應(yīng)的調(diào)整分區(qū)點;
6. 如果分區(qū)點位于數(shù)組的邊界或者分區(qū)點處的元素形成有效的中位數(shù)，我們可以計算兩個數(shù)組的中位數(shù)；
7. 然后，我們計算兩個數(shù)組中分區(qū)左側(cè)的最大元素和兩個數(shù)組中分區(qū)右側(cè)的最小元素，如果較短數(shù)組中分區(qū)左側(cè)的最大元素小于或等于較長數(shù)組中分區(qū)右側(cè)的最小元素 ，并且?較短數(shù)組中分區(qū)右側(cè)的最小元素大于等于較長數(shù)組中分區(qū)左側(cè)的最大元素?，然后表明我們找到了中位數(shù)；
8. 如果合并后數(shù)組的長度是偶數(shù)，我們?nèi)》謪^(qū)左側(cè)最大元素和分區(qū)右側(cè)最小元素的平均值；如果合并后數(shù)組的長度是奇數(shù)，我們?nèi)》謪^(qū)左側(cè)最大元素作為作為中位數(shù)

代碼如下：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    //記錄兩個數(shù)組的長度大小
    int m = nums1.size();
    int n = nums2.size();

    //確保第一個數(shù)組始終是較短數(shù)組
    if (m > n) 
    {
        return findMedianSortedArrays(nums2, nums1);
    }

    //在較短數(shù)組的區(qū)間 【0，m】之間里查找出合適的分區(qū)點
    //使得較短數(shù)組滿足我們需要的條件 
    int left = 0;
    int right = m;

    while (left <= right) {
        //找到較短數(shù)組的分區(qū)點partition1
        int partition1 = (left + right) / 2;
        //利用公式找到較長數(shù)組的分區(qū)點partition2
        int partition2 = (m + n + 1) / 2 - partition1;

        //然后我們檢查分區(qū)點是否在數(shù)組的邊界，如果沒有，我們檢查分區(qū)點處元素是否形成有效的中位數(shù)
        //如果沒有，我們可以相應(yīng)的調(diào)整分區(qū)點

        //較短數(shù)組找到分區(qū)點后，因為數(shù)組是已經(jīng)排好序的
        //當 partition1=0 時，說明較小數(shù)組分割線左邊沒有值，為了不影響
        //nums1[partition1] <= nums2[partition2]和 Math.max(maxLeft1, maxLeft2)的判斷
        //所以將它設(shè)置為int的最小值，即INT_MIN
        int maxLeft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];

        //較短數(shù)組找到分區(qū)點后，因為數(shù)組是已經(jīng)排好序的
        //partition1 等于較小數(shù)組的長度時，說明較小數(shù)組分割線右邊沒有值，為了不影響
        // nums2[partition2] <= nums1[partition1] 和 Math.min(minRight1, minRight2)的判斷，
        //所以將它設(shè)置為int的最大值，即INT_MAX
        int minRight1 = (partition1 == m) ? INT_MAX : nums1[partition1];

        //較長數(shù)組找到分區(qū)點后，因為數(shù)組是已經(jīng)排好序的
        //當partition2等于0時，說明較長數(shù)組分割線左邊沒有值，為了不影響
        // nums2[partition2] <= nums1[partition1] 和 Math.max(maxLeft1, maxLeft2)的判斷，
        //所以將它設(shè)置為int的最小值，即INT_MIN
        int maxLeft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];

        //較長數(shù)組找到分區(qū)點后，因為數(shù)組是已經(jīng)排好序的
        //當partition2 == n，說明較長數(shù)組分割線右邊沒有值，為了不影響
        //nums1[partition1] <= nums2[partition2] 和 Math.min(minRight1, minRight2)的判斷，
        //所以將它設(shè)置為int的最大值，即INT_MAX
        int minRight2 = (partition2 == n) ? INT_MAX : nums2[partition2];
        
        //然后，我們計算兩個數(shù)組中分區(qū)左側(cè)的最大元素和兩個數(shù)組中分區(qū)右側(cè)的最小元素
        //如果較短數(shù)組中分區(qū)左側(cè)的最大元素小于或等于較長數(shù)組中分區(qū)右側(cè)的最小元素 并且
        //較短數(shù)組中分區(qū)右側(cè)的最小元素大于等于較長數(shù)組中分區(qū)左側(cè)的最大元素 ，然后表明我們找到了中位數(shù)
        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            //如果合并后數(shù)組的長度是偶數(shù)，我們?nèi)》謪^(qū)左側(cè)最大元素和分區(qū)右側(cè)最小元素的平均值
            if ((m + n) % 2 == 0)            
            {
                return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
            }
            //如果合并后數(shù)組的長度是奇數(shù)，我們?nèi)》謪^(qū)左側(cè)最大元素作為作為中位數(shù)
            else 
            {
                return max(maxLeft1, maxLeft2);
            }
        } 
        //此處用了maxleft1 < minRight2的取反，當較小數(shù)組中分區(qū)點的左邊的值大于較長數(shù)組中分區(qū)點的右邊的值
        //表面右指針應(yīng)該左移
        else if (maxLeft1 > minRight2)         
        {
            right = partition1 - 1;
        } 
        //滿足條件，左指針繼續(xù)右移到 partition1 + 1位置處
        else 
        {
            left = partition1 + 1;
        }
    }
    return 0.0;
 }
};

性能分析：

• ?時間復(fù)雜度：O(logmin(m,n)))，其中?m 和?n 分別是數(shù)組?nums1?和?nums2的長度。查找的區(qū)間是?[0,m]，而該區(qū)間的長度在每次循環(huán)之后都會減少為原來的一半。所以，只需要執(zhí)行?logm 次循環(huán)。由于每次循環(huán)中的操作次數(shù)是常數(shù)，所以時間復(fù)雜度為?O(logm)。由于我們可能需要交換?nums1?和?nums?2 使得?m≤n，因此時間復(fù)雜度是?O(logmin(m,n)))。
• 空間復(fù)雜度：因為不需要借助額外的空間，因此 空間復(fù)雜度為O(1)。

到此，本題便講解結(jié)束了??！文章來源地址http://www.zghlxwxcb.cn/news/detail-426681.html

到了這里，關(guān)于《LeetCode 熱題 HOT 100》——尋找兩個正序數(shù)組的中位數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！