Majority Problem(过半元素问题)

[问题描述] Majority定义: 整形数组A[1...n]中的元素a, 其出现次数超过 ⌊n/2⌋.

 

这个问题应该是比较经典的问题, 我大概整理了一下几种常见的算法:

 

1. Brute-force ( O(N^2) )

 

这种方法比较直观, 将每个元素A[i]与其后面出现的元素A[i + 1...n]比较, 得到A[i]的出现次数C[i]. C[i]中如果有 > ⌊n/2⌋的元素, 那么元素 A[i]就是majority. 复杂度是O(N^2).

 

 

2. 排序 + 线性遍历 ( O(N*lgN) )

 

排序需要耗费O(N*lgN), 然后在已序的新数组上遍历一次找出满足条件的majority, 耗时O(N).

 

 

3. Median + 线性遍历 (O(N) ~ O(N^2))

 

不管n是奇数还是偶数, 如果存在majority K, 那么在已序的数组中, 其必然有占据 ⌊(n + 1)/2⌋这个位置.

 ⌊(n + 1)/2⌋这个位置的元素是属于median, 于是问题就转换为先求 median of A[1...n]. Selection算法如果采用median-of-medians的pivot选择法, 可以保证即使在worst-case情况下也能O(n) 时间求出median. 此处因为可能会出现大量元素相等的情况, 因此传统的partion方法可能会导致即使尽可能地选取最好的pivot, 也会导致每次partion及其不均衡, 从而导致复杂度及其靠近O(N^2). 通过改进partition的策略应该可以避免这种情况(2分转3分?).

 

随后得到这个元素K以后, 我们线性遍历A一次, 检查K出现的次数是否满足条件, 耗费时间O(N). 

 

 

4. Majority Algorithm ( O(N) )

 

此算法我是在 <Algorithm Design Techniques and Analysis> 中看到的, 线性的. 该算法的关键思想源自以下这条定理:

 

如果元素 x 和 y是不同的元素, 那么移除这两个元素后得到的新数组B[1...n-2], 与A的majority是相等的.

 

有了这条定理, 我们就可以上代码啦:

 

MAJORITY Algorithm

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) 

 

代码中有几个关键之处, 保证了程序的正确性.

 

1. 循环体(11-15): 假定c是majority. 如果 A[j] != c, 根据定理, 去除这两个元素后得到的新序列B, 其Majority依然是c. 但出现次数减一. 否则, 出现次数加一.

 

2. 第16行, 如果从m开始的扫描终止于序列最后一个元素, 则返回c. j = n 时, count的值 >= 0. 对于count > 0, 很容易理解, c在A[m...n]中出现的次数必然超过一半. 而count = 0, c出现的次数刚好一半. 对于A[1...m-1]里面的任何元素, 其出现次数必然<= 1 / 2. 因此, 只有count > 0时候, 返回的元素才是真正的majority. 此处 count = 0的返回, 仅仅是为了有一个序列内的candidate数值作为后续检查使用. 如果candidate返回有效的数组索引, 自然可以避免后续的检查.

 

3.  第17行, j < n. 这个时候, 根据count = 0, 可以得知, A[m...j]中的任何元素,除了c出现一半外, 其它元素出现均小于一半. 因此, 可能的candidate在A[j + 1...n]中必然超过一半.