• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            A Za, A Za, Fighting...

            堅信:勤能補拙

            2011好題 - 尋找倆已排好序數組的中位數

            問題:
            有兩個已排好序的數組A和B,長度均為n,找出這兩個數組的中間元素。要求時間代價為O(logn)

            思路:
            a. 比較自然的思路是歸并算法,不過時間復雜度是O(n),無法滿足題目要求

            b.
            http://www.binghe.org/2011/05/find-median/ )

            Say the two arrays are sorted and increasing, namely A and B.
            It is easy to find the median of each array in O(1) time.
            Assume the median of array A is m and the median of array B is n.
            Then,
            1′ If m=n, then clearly the median after merging is also m, the algorithm holds.
            2′ If m<n, then reserve the half of sequence A in which all numbers are greater than
            m, also reserve the half of sequence B in which all numbers are smaller than n.
            Run the algorithm on the two new arrays.
            3′ If m>n, then reserve the half of sequence A in which all numbers are smaller than
            m, also reserve the half of sequence B in which all numbers are larger than n.

            Run the algorithm on the two new arrays.

            Time complexity: O(logn)






            posted on 2011-10-16 18:38 simplyzhao 閱讀(450) 評論(0)  編輯 收藏 引用 所屬分類: R_找工復習2011

            導航

            <2010年7月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            婷婷久久五月天| 国产亚洲精品美女久久久| 久久www免费人成精品香蕉| 99热都是精品久久久久久| 手机看片久久高清国产日韩| 久久久无码精品亚洲日韩京东传媒 | 久久国产成人午夜aⅴ影院| 热久久最新网站获取| 国产精品久久久久久一区二区三区 | 少妇高潮惨叫久久久久久| 国产精品久久久福利| 一本综合久久国产二区| 精品综合久久久久久97超人| 亚洲国产精品成人久久蜜臀 | 亚洲乱亚洲乱淫久久| 亚洲国产天堂久久久久久| 久久精品欧美日韩精品| 欧洲国产伦久久久久久久| www久久久天天com| 欧美精品乱码99久久蜜桃| 久久久国产精品| 亚洲国产成人久久综合碰碰动漫3d| 精品国产乱码久久久久软件| 国产福利电影一区二区三区久久老子无码午夜伦不 | 国产精品天天影视久久综合网| 日韩欧美亚洲综合久久影院Ds| 久久免费美女视频| 国产成人精品久久免费动漫| 久久人人爽人人爽人人片AV东京热| 伊人久久综在合线亚洲2019| 欧美激情精品久久久久| 久久国产精品成人片免费| 久久青青草原精品国产| 老色鬼久久亚洲AV综合| 热re99久久精品国99热| 久久综合给合久久狠狠狠97色| 久久久久久久久久久精品尤物| 免费精品国产日韩热久久| 国产精品美女久久福利网站| 亚洲欧洲精品成人久久奇米网| 怡红院日本一道日本久久 |