成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

php算法題：尋找有序數(shù)組的中位數(shù)

sPeng / 2355人閱讀

摘要：二二分法求解根據(jù)上面對(duì)中位數(shù)的解釋，以及對(duì)于題目中給出的有序數(shù)組，?？梢韵氲?，最后肯定是的一部分在中位數(shù)的左邊，一部分?jǐn)?shù)在中位數(shù)的右邊，同理。

4. Find Median Sorted Arrays

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

You may assume nums1 and nums2 cannot be both empty.

Example 1:

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

The median is 2.0

Example 2:

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

The median is (2 + 3)/2 = 2.5
一、按時(shí)間復(fù)雜度O（m+n）解 先來解釋一下什么是中位數(shù) 
如下：
[3，4，5] , 那么這組數(shù)的中位數(shù)就是4
[3，4，5，6] , 那么這組數(shù)的中位數(shù)就是 （4+5）／2 = 4.5

開始沒有注意到時(shí)間復(fù)雜度，但按照O（m+n）解，也花了我不少時(shí)間，可能是很久沒有接觸算法的緣故。

二、二分法求解

根據(jù)上面對(duì)中位數(shù)的解釋，以及對(duì)于題目中給出的有序數(shù)組nums1[m]，nums2[n]?？梢韵氲?，最后肯定是nums1的一部分在中位數(shù)的左邊，一部分?jǐn)?shù)在中位數(shù)的右邊，nums2同理。

所以咱們可以將nums1和nums2，合并后劃分成，左右兩個(gè)數(shù)組。

nums1[0],...,nums1[i-1] | nums1[i] ... nums1[m-1]
nums2[0],...,nums2[j-1] | nums2[j] ... nums2[m-1]

也可以看成是下面這種

nums1[0],...,nums1[i-1]，nums2[0],...,nums2[j-1] | nums1[i] ... nums1[m-1]，nums2[j] ... nums2[m-1]

左右兩個(gè)數(shù)組的總數(shù)可能是奇數(shù)，也可能是偶數(shù)。所以規(guī)定，如果是奇數(shù)，那么左邊比右邊多一個(gè)，如果是偶數(shù)，那么左右兩邊相等。

這里來說一下i和j的關(guān)系
左邊數(shù)組的個(gè)數(shù) t =（int)(m+n+1)/2
j = t - i.

理解清楚了i和j的關(guān)系之后，那么接下來就要判斷中位數(shù)了
抓住數(shù)組有序這個(gè)條件。
可知如果滿足中位數(shù)的條件左邊最大的數(shù)leftMax 小于 右邊最小的數(shù)rightMin
并且左邊數(shù)組個(gè)數(shù)一定是等于右邊數(shù)組個(gè)數(shù)，或者是比右邊數(shù)組個(gè)數(shù)多1個(gè)。

最重要的來了
根據(jù)上面一系列的條件，那么現(xiàn)在要做的就是通過二分法選出合適的i，進(jìn)而得到中位數(shù)

還得考慮邊界問題，這個(gè)在下面代碼中給出注釋

代碼如下：

class Solution{
    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Float
     */
    function findMedianSortedArrays($nums1, $nums2) {
        $m = count($nums1);
        $n = count($nums2);
        //如果$m>$n時(shí)，后面的$j會(huì)可能小于0。也就是上面提到的不等式（ t =（int)(m+n+1)/2。j = t - i.）
        if($m>$n) return $this->findMedianSortedArrays($nums2,$nums1);
        
        $t = (int)(($m+$n+1)/2);
        $i = 0;
        $j = 0;
        
        /** 要理解清楚下面兩組max，min的意思 */
        $leftMax = 0;//左邊數(shù)組的最大值
        $rightMin = 0;//右邊數(shù)組的最小值
        $iMax = $m;//二分法的右邊界
        $iMin = 0;//二分法的左邊界
        
        while($iMax >= $iMin){
            //二分法
            $i = (int)(($iMax+$iMin)/2);
            $j = $t-$i;
            if ($i>0 && $j<$n && $nums1[$i-1] > $nums2[$j]){//利用數(shù)組有序，可以只比較一次
                $iMax=$i-1;
            }elseif ($j>0 && $i<$m && $nums1[$i] < $nums2[$j-1]){//利用數(shù)組有序，可以只比較一次
                $iMin=$i+1;
            }else{//二分到最后 最佳位置
                if ($i==0){
                    $leftMax = $nums2[$j-1];
                }elseif ($j==0){
                    $leftMax = $nums1[$i-1];
                }else {
                    $leftMax = max($nums2[$j-1],$nums1[$i-1]);
                }
                if(($m+$n)%2 == 1){//數(shù)組和是奇數(shù)
                    return $leftMax;
                }
                //數(shù)組和是奇數(shù)
                if ($i == $m){
                    $rightMin = $nums2[$j];
                }elseif ($j == $n){
                    $rightMin = $nums1[$i];
                }else {
                    $rightMin = min($nums2[$j],$nums1[$i]);
                }
                return ($leftMax+$rightMin)/2;
            }
        }        
    }
    }
總結(jié)

講解問題的能力還有待進(jìn)一步提高。如果有問題歡迎私聊。

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/31581.html

相關(guān)文章

  • JS算法題之leetcode(1~10)

    摘要：先去空白，去掉空白之后取第一個(gè)字符，判斷正負(fù)符號(hào)，若是英文直接返回，若數(shù)字則不取。回文數(shù)題目描述判斷一個(gè)整數(shù)是否是回文數(shù)?；匚臄?shù)是指正序從左向右和倒序從右向左讀都是一樣的整數(shù)。 JS算法題之leetcode(1~10) 前言 一直以來，前端開發(fā)的知識(shí)儲(chǔ)備在數(shù)據(jù)結(jié)構(gòu)以及算法層面是有所暫缺的，可能歸根于我們的前端開發(fā)的業(yè)務(wù)性質(zhì)，但是我認(rèn)為任何的編程崗位都離不開數(shù)據(jù)結(jié)構(gòu)以及算法。因此，我作為...

    SoapEye 評(píng)論0 收藏0

  • ??思維導(dǎo)圖整理大廠面試高頻數(shù)組10: 3種方法徹底解決中位數(shù)問題, 力扣4??

    此專欄文章是對(duì)力扣上算法題目各種方法的總結(jié)和歸納, 整理出最重要的思路和知識(shí)重點(diǎn)并以思維導(dǎo)圖形式呈現(xiàn), 當(dāng)然也會(huì)加上我對(duì)導(dǎo)圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(diǎn)(不用每次都重復(fù)看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經(jīng)知道解題思路和方法, 想進(jìn)一步加強(qiáng)理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據(jù)題號(hào)先去力扣看看官方題解, 然后再看本文內(nèi)容). 關(guān)...

    XanaHopper 評(píng)論0 收藏0

  • LeetCode4.尋找兩個(gè)有序數(shù)組的中位數(shù) JavaScript

    摘要：尋找兩個(gè)有序數(shù)組的中位數(shù)給定兩個(gè)大小為和的有序數(shù)組和。請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù)，并且要求算法的時(shí)間復(fù)雜度為。你可以假設(shè)和不會(huì)同時(shí)為空。示例則中位數(shù)是示例則中位數(shù)是答案參考排序中位數(shù) LeetCode4.尋找兩個(gè)有序數(shù)組的中位數(shù) JavaScript 給定兩個(gè)大小為m和n的有序數(shù)組nums1和nums2。請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù)，并且要求算法的時(shí)間復(fù)雜度為 O(log(m +...

    habren 評(píng)論0 收藏0

  • 前端 100 問：能搞懂80%的請(qǐng)把簡歷給我

    摘要：解析第題第題為什么的和的中不能做異步操作解析第題第題京東下面代碼中在什么情況下會(huì)打印解析第題第題介紹下及其應(yīng)用。盡量減少操作次數(shù)。解析第題第題京東快手周一算法題之兩數(shù)之和給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值，找出數(shù)組中和為目標(biāo)值的兩個(gè)數(shù)。 引言 半年時(shí)間，幾千人參與，精選大廠前端面試高頻 100 題，這就是「壹題」。 在 2019 年 1 月 21 日這天，「壹題」項(xiàng)目正式開始，在這之后每個(gè)工...

    Scott 評(píng)論0 收藏0

  • LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

    摘要：每天會(huì)折騰一道及以上題目，并將其解題思路記錄成文章，發(fā)布到和微信公眾號(hào)上。三匯總返回目錄在月日月日這半個(gè)月中，做了匯總了數(shù)組知識(shí)點(diǎn)。或者拉到本文最下面，添加的微信等會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

    tracy 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<