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

            Fly me to the moon

            the beauty of C++

            wrong

                感謝Will同學指出的問題,我仔細思考后發現不只是代碼的問題,算法思想上就有錯了,我沒有在每次交換后保持兩個子序列的有序性,這樣就無法保證i和j指向正確的位置,而如果想要保持子序列有序,雖然可以引入一個臨時變量并通過交換實現,但算法復雜度就不是線性的了,所以結論是暫時沒有可以簡單實現的線性時間原地歸并。事實上,有一些paper描述了很多線性時間原地歸并的算法,但是復雜度都相當高,感興趣的朋友可以自行google。
                為了不誤導大家,把題目改了,至于下面的筆試題,希望牛人給予解答啊,謝謝。

            ---------------------------------------原文分割線-----------------------------------------------
                快要找工作了,現在在回顧一些算法和數據結構的知識,除了看書,爭取每天挑一兩道有趣的題目來練練手。本人沒參加過ACM,解算法題的實力也相當菜鳥,但本人對于任何能夠鍛煉思維能力的題目都相當熱衷,不怕做不出來,就怕不敢做,做多了,思考多了,總是有幫助的,呵呵,所以希望各位看到我的文章中有錯誤的地方請不吝賜教,在下感激不盡。
            Share is happiness.

                今天的題目是在網上看到的,ms是一道baidu的筆試題:
                給定一個序列a[0...n-1]和一整數m,滿足0<=m<=n-1,且a[0...m-1]和a[m...n-1]都為有序子序列,要求設計一個時間復雜度為O(N),空間復雜度為O(1)的算法,實現將這兩個子序列合并為一個完整的有序序列a[0...n-1]。

                題意很簡單,就是要設計一個線性時間的原地歸并算法,我給出的思路:
                從左到右遍歷數組,將當前未遍歷元素中的最小值置換到它所應在的位置。這個簡單的描述有點像選擇排序,但選擇排序O(N^2)的復雜度明顯是不允許的,這里,利用兩個子序列已有序的性質,我們可以設計更高效的O(N)算法:首先易知未遍歷元素中的最小值必定是兩個子序列的最小值中的更小者,將改值交換到它應在的位置;利用有序性,可以在遍歷過程中分別記錄兩個子序列的當前最小元素的位置,這樣就省去了選擇排序中每次都要遍歷剩余序列找出最小值的開銷,每次遍歷內部為常數次的比較和交換操作,所以整個算法的時間復雜度為O(N)。

            posted on 2009-09-16 11:07 翼帆 閱讀(477) 評論(2)  編輯 收藏 引用 所屬分類: 算法

            評論

            # re: 線性時間原地歸并[未登錄] 2009-10-05 01:24 Will

            程序有點問題:
            比如{4,5,1,2,3}  回復  更多評論   

            # re: wrong 2009-10-05 11:57 翼帆

            謝謝Will  回復  更多評論   

            導航

            <2025年5月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            統計

            常用鏈接

            留言簿

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久噜噜噜www成人网| 精品免费tv久久久久久久| 亚洲午夜久久久| 亚洲精品无码久久久久去q| 亚洲AV无码一区东京热久久| 久久精品成人国产午夜| 久久久精品国产免大香伊| 久久精品国产福利国产秒| 国产精品中文久久久久久久| 国产一级做a爰片久久毛片| 国产精品久久久久久久app| 99999久久久久久亚洲| 久久www免费人成看国产片| 亚洲欧美成人综合久久久| 久久久久夜夜夜精品国产| 国产成人精品久久| 久久免费视频6| 久久精品成人免费网站| 性欧美丰满熟妇XXXX性久久久| 99久久精品国产综合一区| 久久99久久99精品免视看动漫| 人妻丰满?V无码久久不卡| 久久精品国产亚洲沈樵| 人妻无码久久一区二区三区免费| 久久午夜综合久久| 激情五月综合综合久久69| 国产亚洲欧美成人久久片| 人人狠狠综合久久88成人| 97久久婷婷五月综合色d啪蜜芽| 久久精品国产精品亚洲下载| 97久久精品国产精品青草| 色偷偷久久一区二区三区| 99精品国产综合久久久久五月天 | 精品久久久久国产免费| 久久久久久国产精品无码超碰| 亚洲国产成人久久一区WWW| 人妻丰满?V无码久久不卡| 午夜精品久久久久久久无码| 久久国产午夜精品一区二区三区| 久久久久久a亚洲欧洲aⅴ| 精品久久久无码人妻中文字幕豆芽|