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.cppblog.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 阅读(1083) 评论(0)  编辑 收藏 引用 所属分类: 解题报告