• <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)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            国产69精品久久久久久人妻精品| 91精品国产色综合久久| 久久久精品人妻无码专区不卡| 很黄很污的网站久久mimi色| 看全色黄大色大片免费久久久| 久久精品国产亚洲av麻豆蜜芽| 韩国三级大全久久网站| 国产精品伊人久久伊人电影| 久久午夜免费视频| 狠狠狠色丁香婷婷综合久久俺| 久久久国产精品| 97久久精品无码一区二区| 久久久久女教师免费一区| 久久精品aⅴ无码中文字字幕不卡 久久精品aⅴ无码中文字字幕重口 | 色偷偷91久久综合噜噜噜噜| 亚洲va久久久噜噜噜久久| 精品无码人妻久久久久久| 人妻精品久久久久中文字幕69| 久久99精品国产99久久6| 男女久久久国产一区二区三区| 久久精品中文字幕有码| 国产三级久久久精品麻豆三级 | 国产日韩久久免费影院| 国产亚洲精久久久久久无码77777| 国内精品久久久久久久coent| 蜜臀av性久久久久蜜臀aⅴ| 精产国品久久一二三产区区别| 久久99精品久久久久久噜噜| 亚洲国产精品热久久| 久久精品国产免费一区| 99久久免费国产特黄| 国内精品久久久久久久97牛牛| 久久天天躁狠狠躁夜夜96流白浆| 久久这里的只有是精品23| 国产欧美久久久精品影院| 亚洲国产成人久久一区WWW| 亚洲国产高清精品线久久| 国内精品久久久久影院亚洲 | 久久精品无码午夜福利理论片| 亚洲色欲久久久综合网| 亚洲va中文字幕无码久久|