成年人AV线,九九九九性欲视频,国内无码一区二区三区

題目描述

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

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

你可以假設(shè) nums1 和 nums2 不會同時為空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

則中位數(shù)是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

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

題目解析

解決這個問題，我們必須要搞清楚兩個問題：

兩個數(shù)組都是有序數(shù)組，數(shù)組的元素都是從小到大排列的
中位數(shù)的定義：在中學(xué)數(shù)學(xué)中，我們可能學(xué)習(xí)過中位數(shù)的定義，但在統(tǒng)計學(xué)中，中位數(shù)還有這樣一種解釋：

中位數(shù)：當(dāng)一個數(shù)可以將一個集合劃分成兩個長度相等的子集，其中一個子集中的元素總是大于另一個子集中的元素，那么這個數(shù)就稱為集合的中位數(shù)。

這個題目的難點在于，給你一個有序數(shù)組，你肯定會求中位數(shù)。給你兩個數(shù)組，你肯定也能想辦法用暴力法解出來，但暴力求解，復(fù)雜度一定是超過 $O(log(m+n))$ 的！

這個題目是查找兩個有序數(shù)組的中位數(shù)，我們能想到的 $O(log(...))$ 級別的查找算法，恐怕只有二分查找了。

二分查找法是用于解決一個數(shù)組的查找問題的，那么如何解決兩個數(shù)組的問題呢？還是有一些情況需要討論！

解法：二分查找法

從前面中衛(wèi)數(shù)的定義來看，我們的出發(fā)點，應(yīng)該是劃分而不是遍歷。

那么具體應(yīng)怎么劃分呢？假設(shè)有兩個有序數(shù)組A、B，長度分別為m、n:

首先，讓我們在任一位置 $i$ 將 $A$ 劃分成兩個部分（注意A[i]在右邊這個集合）：

          left_A             |        right_A
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]

不難得出： $len(left\_A)=i, len(right\_A)=m-i, i \in [0, m]$

同樣我們在位置 $j$ 對 $B$ 進(jìn)行劃分：

          left_B             |        right_B
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

同理： $len(left\_B)=j, len(right\_B)=n-j, j \in [0, n]$

將兩個數(shù)組的左右部分都合并起來，形成總體的兩個左右子集：

          left_part          |        right_part
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

如果i和j的取值足夠合適，使得：

$len(left\_part) = len(right\_part)$

$max(left\_part) \le min(right\_part)$

那么我們就可以找到這個中位數(shù)，它就等于:
$\frac{max(left\_part)+min(right\_part)}2$

上面的兩個條件，等價于：

$i+j=m-i+n-j \Rightarrow j=\frac{m+n}2$
$B[j-1] \le A[i], A[i-1] \le B[j]$

這里有幾點需要說明：

這里我們假設(shè) $A[i-1], B[j-1], A[i], A[j]$ 始終存在，也就是說 $i \notin \{0, m\}, j \notin \{0, n\}$ , 這種極端情況我們最后來討論

這里設(shè) $n \ge m$ ，因為 $i, j$ 都必須是非負(fù)數(shù)，且 $j = \frac{m+n+1}2 - i$ , 當(dāng) $n \lt m$ 時，左邊的表達(dá)式有可能小于0

條件2中的兩個子條件，不可能同時不滿足，請自己思考原因

所以，我們的任務(wù)就是：

在 $[0, m]$ 中搜索 $i$ ，使得 $B[j-1] \le A[i], A[i-1] \le B[j]$ , 其中 $j=\frac{m+n+1}2-i$

現(xiàn)在，我們已經(jīng)把一個雙數(shù)組遍歷問題，變成了對一個變量的搜索問題！

接下來，我們來具體設(shè)計我們的二分算法：

設(shè) $imin=0, imax=m$ ，它們夾成了一個 $i$ 的初始搜索區(qū)間
在二分查找法中，被查找的 $i$ 應(yīng)該賦予這個區(qū)間的中值，即 $i=\frac{imin+imax}2$ , 那么 $j$ 也可以根據(jù) $j = \frac{m+n+1}2$ 求得一個值
現(xiàn)在我們來檢查上面的條件2是否滿足，一共有3種情況：
- $B[j-1] \le A[i], A[i-1] \le B[j]$ 這表明 $i$ 已經(jīng)搜索到了目標(biāo)值，結(jié)束搜索
- $B[j-1] \gt A[i]$ ：這意味著 $i$ 太小了，目標(biāo)值應(yīng)該在 $[i+1, imax]$ 之間，因此設(shè) $imin=i+1$ ，返回步驟2
- $A[i-1] \gt B[j]$ ：這意味著 $i$ 太大了，目標(biāo)值應(yīng)該在 $[imin, i-1]$ 之間，因此設(shè) $max = i-1$ ，返回步驟2

最后，我們來討論一下剛才忽略的臨界情況：

這里我們要證明一下 $i$ 與 $j$ 的取值關(guān)系

由于 $n \ge m$ ,

$i \le m \Rightarrow j = \frac{m+n}2 - i \ge \frac{2m}2 - i \ge 0$ , 當(dāng)且僅當(dāng) $i=m$ 時， $j =0$

同理可證 $i \ge 0 \Rightarrow j \le n$ , 當(dāng)且僅當(dāng) $i = 0$ 時， $j=n$

這意味著，在判斷臨界情況時，我們只需關(guān)心 $i$ 的取值， $i$ 為臨界值， $j$ 也一定取臨界值

還意味著， $A[i-1], B[j-1]$ 必然有一個是存在的， $A[i], B[j]$ 也必然有一個是存在的！

還沒完！

現(xiàn)在我們只是找到了最佳劃分，還沒有搞清楚哪個值是中位數(shù)！

現(xiàn)在，我們已經(jīng)把A和B劃分成了合適的left_part和right_part兩個子集

      left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

那么，中位數(shù)只能在 $max(left\_part)$ 和 $min(right\_part)$ 中產(chǎn)生

由于 $j = \frac{m+n}2-i$ ，且在C++中，整數(shù)除法會舍棄小數(shù)，向下取整。

當(dāng) $m+n$ 為奇數(shù)的時候，雖然我們的條件 $j = \frac{m+n}2-i$ 使得 $len(left\_part)=len(right\_part)$ ，但由于C++向下取整的特性，兩邊長度的條件并不會成立，實際上某一部分會比另一個部分多出一個元素。多出的那個元素，就是我們要找的中位數(shù)。

C++的特性，實際上是縮小了 $j$ 的取值， $i$ 的取值也會在循環(huán)中間接縮小一點，所以中位數(shù)一定是在right_part里面！

即: $median = min(A[i], B[j])$
當(dāng) $m+n$ 為偶數(shù)，就很容易了， $median = (max(left\_part) + min(right\_part)) *0.5$

至此，我們需要討論的點已經(jīng)全部清楚了，怎么樣，這就是LeetCode的“魅力”！

代碼：

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

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        const int m = nums1.size();
        const int n = nums2.size();
        if(m > n) return findMedianSortedArrays(nums2, nums1);//我們是假設(shè)n>=m的
        const int k = (m + n) / 2;
        int imin = 0;
        int imax = m;
        while(imin <= imax){
            int i = (imin + imax) / 2;
            int j = (k-i);
            if (i < imax && nums2[j-1] > nums1[i]){
                imin = i + 1; // i 太小了
            }
            else if (i > imin && nums1[i-1] > nums2[j]) {
                imax = i - 1; // i 太大了
            }
            else{
                //此時i剛剛好
                //我們用INT_MIN, INT_MAX(相當(dāng)于無窮小和無窮大)來代替不存在的情況
                int maxLeft = max(i <= 0 ? INT_MIN : nums1[i-1],
                    j <= 0 ? INT_MIN : nums2[j-1]);
                if((m + n) % 2 == 1)
                    return maxLeft;
                
                int minRight = min(i >= m ? INT_MAX: nums1[i],
                    j >= n ? INT_MAX : nums2[j]);
                return (maxLeft + minRight) * 0.5;
            }
        }
        return 0.0;
    }
};

復(fù)雜度分析

時間復(fù)雜度： $O(log(min(m, n)))$ ，因為查找的空間每次都會縮短為原來的一半，且這個空間的初始長度取決于m, n的最小值
空間復(fù)雜度： $O(1)$ 我們只使用了一些局部變量，沒有引入新的內(nèi)存來存放數(shù)組

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

LeetCode實戰(zhàn)004 尋找兩個有序數(shù)組的中位數(shù)

LeetCode實戰(zhàn)004 尋找兩個有序數(shù)組的中位數(shù)

題目描述

題目解析

解法：二分查找法

復(fù)雜度分析

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

LeetCode實戰(zhàn)004 尋找兩個有序數(shù)組的中位數(shù)

題目描述

題目解析

解法：二分查找法

復(fù)雜度分析

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av