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://m.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 閱讀(1122) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告