• <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久久精品无码一区二区毛片| 亚洲成人精品久久| 久久亚洲国产精品123区| 中文字幕无码av激情不卡久久| 久久精品一本到99热免费| 久久精品国产一区| 蜜桃麻豆WWW久久囤产精品| 99精品久久精品| 久久精品国产男包| 狠狠色综合久久久久尤物| 欧美大香线蕉线伊人久久| 久久久久亚洲爆乳少妇无| 久久99精品久久久久久hb无码| 日本精品久久久久影院日本| 三上悠亚久久精品| 日韩欧美亚洲综合久久| 国产呻吟久久久久久久92| 精品国产一区二区三区久久久狼 | 久久精品国产久精国产| 久久天天躁夜夜躁狠狠躁2022| 精品久久久久久无码人妻热| 99久久精品国产麻豆| 久久人人爽人人爽人人AV| 久久乐国产精品亚洲综合| 91精品久久久久久无码| 精品九九久久国内精品| 国内精品伊人久久久久av一坑| 久久婷婷激情综合色综合俺也去 | 欧美久久久久久| 亚洲国产小视频精品久久久三级| 欧美久久精品一级c片片| 久久久一本精品99久久精品66| 伊人久久大香线蕉av不变影院| 中文国产成人精品久久亚洲精品AⅤ无码精品 | 成人国内精品久久久久一区| 色偷偷偷久久伊人大杳蕉| 亚洲国产另类久久久精品小说| 亚洲精品tv久久久久久久久|