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

            Why so serious? --[NKU]schindlerlee

            Majority Problem:給出n個物品,判斷是否有超過一半的物品是相同的。


            給出n個物品,判斷是否有超過一半的物品是相同的。
            前提是,兩個物品只有放到一個特殊的裝置中才能判斷是否相同。

            Θ(n^2):brute force
                對每一個物體遍歷
            Θ(nlogn):分治,下面的代碼純屬表達思想用,沒有測試!!!
                int divide(int *a,int n)
                {
                    if(n == 2) {
                        if(a[0] == a[1]) {
                            return a[0];
                        }
                        return EMPTY;
                    }
                    int ca = divide(a,n/2);
                    int cb = divide(a + n/2.n - n/2);
                    if(ca != EMPTY) {
                        if(ca is majority in a[n/2 ... n-n/2]) {
                            return ca;
                        }
                    }
                    if(cb != EMPTY) {
                        if(cb is majority in a[0...n/2]) {
                            return cb;
                        }
                    }
                    return EMPTY;
                }

            Θ(n):規模下降
            Lemma:如果兩個物品不同那么在去掉這兩個物品的剩余物品中,如果存在Majority
                元素,那么這個元素也是去掉之前的解.
            設考慮要去掉的兩個物品是A,B
                如果A,B都不是Majority元素,那么在去掉A,B之后Majority元素一定不變
                如果A是Majority元素,那么去掉兩個元素之后,在n-2個物品中原來的Majority物品個數
                    由n/2 + 1變為 n/2,依然在n-2個物品中占大多數

            貼<<Algorithms Design Techniques and Analysis>>上的代碼,哥親自輸入的,
            我的技術博客http://www.shnenglu.com/schindlerlee

            Algorithm 5.9 MAJORITY
            Input:An array A[1...n] of n elements.
            Output:The majority element if it exists:otherwise non.

             1. c ← candidate(1)
             2. cout ← 0;
             3. for j ← 1 to n
             4.        if A[j] == c then count ← count + 1
             5. end for
             6. if count > ⌊n/2⌋ then return c
             7. else return none
             8.
             9. Procedure candidate(m)
            10. j ← m;c ← A[m];count ← 1
            11. while j < n and count > 0
            12.     j ← j + 1
            13.     if A[j] == c then count ← count + 1
            14.     else count ← count - 1
            15. end while
            16. if j == n then return c
            17. else return candidate(j + 1)        


            posted on 2009-12-18 18:04 schindlerlee 閱讀(1114) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            日韩一区二区三区视频久久| 久久人人爽人人澡人人高潮AV| 欧美精品九九99久久在观看| 人妻丰满?V无码久久不卡| 无码国内精品久久人妻麻豆按摩 | 久久精品亚洲日本波多野结衣| 一本久道久久综合狠狠爱| 久久99中文字幕久久| 久久成人国产精品一区二区| 亚洲∧v久久久无码精品| 久久996热精品xxxx| 77777亚洲午夜久久多人| 久久免费视频网站| 伊人久久大香线蕉av一区| 久久99精品久久久久久不卡| 久久天天躁狠狠躁夜夜avapp| 精品国产91久久久久久久a| 一本久道久久综合狠狠爱| 色婷婷狠狠久久综合五月| 国产成人久久激情91| 久久精品国产久精国产一老狼| 青青草国产成人久久91网| 欧洲精品久久久av无码电影| 四虎亚洲国产成人久久精品| 91久久九九无码成人网站| 77777亚洲午夜久久多喷| 日韩av无码久久精品免费| 无码人妻久久一区二区三区蜜桃| 国产叼嘿久久精品久久| 人人狠狠综合久久亚洲婷婷| 久久99国内精品自在现线| 蜜臀av性久久久久蜜臀aⅴ| 久久久久久国产a免费观看黄色大片| 国产精品无码久久四虎| 久久99亚洲综合精品首页| 久久精品国产只有精品66| 国产精品成人无码久久久久久| 久久精品国产免费| 94久久国产乱子伦精品免费| 亚洲国产精品久久66| 久久av高潮av无码av喷吹|