题目来自https://oj.leetcode.com/problems/majority-element/。

分析部分摘抄自《线性时间查找固定频率的元素》，有改写。

题目

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

分析

题目大意：

已知一个长度为n的数组，求出现半数以上的元素。

这道题目看似简单，其实得到完美的答案并不容易。首先，不难想到，出现半数以上的元素最多只有一个。而为了选出出现次数达到半数以上的元素，最笨的方法当然就是对数组中出现的每一个元素，都遍历一遍数组记录下其出现频率，通过与[latex]\frac{n}{2}[/latex]比较确定是否符合要求。这样就可以在[latex]O(n^2)[/latex]的时间内，用O(1)空间解决问题。 稍好的方法是用散列表来存储每个元素出现的次数。这个方法的时间复杂度和空间复杂度都是O(n)。

现在问题来了，有没有时间复杂度O(n)空间复杂度O(1)的算法呢？其实早在1991年就有人专门就这个问题发表了论文，介绍了一种线性时间的算法：Majority Vote Algorithm。通过名字就可以看出，这个算法是专门用来解决这个问题的。而由于作者是J Moore (目前是Utexas的计算机系主任)，这个算法有时候也会被称为Moore’s Voting Algorithm (当然这个Moore并不是提出Moore’s Law的那个Gordon Moore)。

算法有两个阶段：配对、计数。在配对阶段，将两个不同的元素配对，直到剩下的元素全部相同。剩下的元素为e。则最后扫描一遍数组，看e出现次数到底有没有超过半数。

以下是代码。

[code lang=”cpp”]
int majorityElement(vector<int> &num) {
int cand;
int unpairedElementCount = 0;
int n = int(num.size());
for (int i = 0; i < n; i++){
if (unpairedElementCount == 0){
cand = num[i];
unpairedElementCount++;
}
else if (num[i] == cand){
unpairedElementCount++;
}
else
unpairedElementCount–;
}
return cand;
}
[/code]

例子

index  0 1 2 3 4 5 6
       2 3 9 9 4 9 9
cand   2   9       
   k   1 0 1 2 1 2 3

unpairedElementCount在图例中记为k。

在算法执行过程中，我们记录一个候选元素cand及尚未配对的元素数量unpairedElementCount。这里重点解释一下unpairedElementCount变量。为什么这个变量名这么长这么拗口呢？为什么不直接叫c、n、k、count呢？因为名字短了你不知道它什么意思啊！！
unpairedElementCount变量记录了，当第i次循环完成后，从0到i位置有多少尚未配对的元素。在上例中

• 当i=0循环完成，unpairedElementCount=1，因为元素2没有与任何元素配对。
• 当i=1循环完成，unpairedElementCount=0，因为元素3与元素2配对。没有尚未配对的元素。
• 当i=4循环完成，unpairedElementCount=1，因为2、3配对，9、4配对。索引位置3的元素9尚未配对。

正确性证明

算法证明的其中一项重要手段是寻找循环不变量。此解法的循环不变量是：

访问后第i（[latex]1\leqslant i \leqslant n[/latex]）个元素后，第i个及之前的元素可以分为两组，一组A全是cand，基数（集合中元素的数量）为k（unpairedElementCount）；另一组B为二元组的集合，每个二元组中的两个值不同。

设数组为X，下面用数学归纳法证明：

• 当1循环完成，[latex]A_1=X[1][/latex]，[latex]B_1=\emptyset[/latex]。循环不变量成立。
• 假设i循环完成，循环不变量成立，设A组为[latex]A_i[/latex]，基数为[latex]k_i[/latex]，B组为[latex]B_i[/latex]。
• • 如果此时[latex]k_i=0[/latex]，即[latex]A_i=\emptyset[/latex]，[latex]B_i=X[/latex]。那么[latex]i+1[/latex]循环中，cand=X[i+1]，[latex]k_{i+1}=1[/latex]。[latex]A_{i+1}=\left \{ X[i+1] \right \}[/latex]，[latex]B_{i+1}=B_i[/latex]。所以循环不变量成立。
  • 如果此时[latex]k_i> 0[/latex]，
  • • 如果X[i+1]==cand，[latex]k_{i+1}=k_i+1[/latex]。那么[latex]A_{i+1}=A_i \cup \left \{ X[i+1] \right \}=A_i \cup \left \{ cand \right \}[/latex]，[latex]B_{i+1}=B_i[/latex]。循环不变量成立。
    • 如果[latex]X[i+1] \neq cand[/latex]，[latex]k_{i+1}=k_i-1[/latex]。[latex]A_{i+1}=A_i-cand [/latex]，[latex]B_{i+1}=B_i\cup \left \{ (cand, X[i+1]) \right \}[/latex]。（从[latex]A_i[/latex]里拿出一个元素，与X[i+1]组成二元组塞进[latex]B_{i+1}[/latex]）循环不变量成立。

在Moore大牛的主页上有针对这个算法的一个演示，感兴趣的同学可以直接移步观看。

更一般的情况

那么，如果我们想找的并不是超过半数的元素，而是出现频率超过一定频率的元素都要找出来，是否也存在一个类似的线性时间的算法呢?答案是肯定的。实际上，这一类从特定的数据集中找出出现频率超过某个阈值的元素的问题，有一个形象的名字叫做Iceberg query，或者叫做host list分析。而Richard Karp 老爷子当年就专门写了一篇论文来讨论这种一般性问题的解决方案，而通过下文的介绍，大家也可以发现，Karp的方案应该也是受到了Moore的算法的启发。

首先还是看一下问题的形式化定义吧:

对于一个序列 [latex]A=( a_1, a_2, \cdots, a_n )[/latex]以及一个在(0,1)之间的实数[latex]\theta[/latex]。假定f(e)表示元素e的出现频率，我们需要找到所有满足[latex]f(e)>\theta n[/latex]的元素。

首先，满足条件的元素个数t必然小于[latex]\frac{1}{\theta}[/latex]。否则的话，[latex]\sum_{c\in A} f(c)>t\theta n\geqslant \frac{1}{\theta}\theta n=n [/latex]。因此，如果令[latex]k=\left \lceil \frac{1}{\theta}-1 \right \rceil[/latex]，我们可以知道最终的候选元素的个数不会超过k。与上文中介绍的算法相同，我们还是基于序列的遍历来完成新的算法。同样的，我们需要维护一个规模为k的候选元素表，其中存储候选元素c以及其出现频率f(c)。遍历开始前，所有的f(c)初始化为0。在遍历过程中:

• 若A[i]已在候选表中，即存在c使得c==A[i]，那么f(c) += 1。
• 若A[i]不在候选表中，且候选表仍有空位，即|T|<K，那么将A[i]插入到表中，且f(A[i]) = 1。
• 若A[i]不在候选表中，且候选表已满。那么丢弃A[i]，且对于候选表中每一元素，做f(c) -= 1。该操作完毕之后，所有f(c)归零的元素从候选表中移除。

算法介绍完了，我们先来证明下其正确性。

首先，false positive的情况可以通过对序列做第二次遍历，同时记录候选元素的出现次数来排除。

然后，我们来排除false negative的情况，也就是说，对于元素c没有出现在候选元素表中，那么一定有[latex]f(c)\leqslant  \theta N[/latex]。可以注意到，算法中的第三步，实际上相当于从目前遍历过的元素中移除K+1个，其中K个是候选表中元素，1个是当前元素。而如果c最终不在候选表中，那么要么c从来没有被选中过，要么是选中后又被排除了。对于前者，c一直扮演着第三步中当前A[i]的角色，被直接丢弃; 对于后者，c可能还扮演着第三步候选表中元素的角色，频率自减1。但不管怎样，可以肯定的是，每次丢弃c，都有另外K个元素也一起被丢弃。假定[latex]f_x(c)[/latex]表示元素c的总体出现频率，由于元素c最终不在候选表中，我们可以认定所有的c都被丢弃掉，也就是说，我们一共丢弃了[latex]f_x(c)(K+1)[/latex]个元素。又[latex]K\leqslant  \frac{1}{\theta}-1[/latex]，我们有[latex]f_x(c)/\theta\leqslant  f_x(c)(K+1) \leqslant N[/latex] ，继而得到[latex]f_x(c)\leqslant  \theta N[/latex]。也就是说，false negative的情况也被排除了。

那么，这个算法的复杂度是多少呢? 由于采用了hash表，我们需要[latex]O\left (\frac{1}{\theta} \right )[/latex]的空间。同时如果假定存取操作都可以O(1)完成的话，算法中的三个步骤时间复杂度分别是O(1), O(1) 和O(K)。然而如果使用平摊分析，我们可以在第一步和第二步都多计一个credit，用于今后可能进行的第三步中的删除操作，那么每一步的平摊时间代价就是O(1)，从而可以在O(N)时间内完成该算法。

三、看平摊分析不顺眼？

看样子对于一般性的iceberg query问题，我们也已经成功给出了一个比较完美的答案，复杂度为O(N)的时间，[latex]O\left (\frac{1}{\theta} \right )[/latex]的空间。无论是时间和空间，都是没有办法再少了。事情到了这个地步，似乎已经可以结束了。但是要注意的是，对于时间复杂度，我们采用的是平摊分析，虽然也是O(N)没错，但看上去总是不太爽(其实我还可以接受了…)。比如说如果在处理当前元素时，走到了上述算法的第3个分支， 那复杂度显然是与当前候选表中元素个数相关的，也就是说[latex]O\left (\frac{1}{\theta} \right )[/latex]。那么，能不能想想办法，使得无论走哪个分支，都只用O(1)的时间复杂度，同时继续保持[latex]O\left (\frac{1}{\theta} \right )[/latex]的空间呢?

其实很容易就想到一个小trick来解决这个问题。第三个分支所做的，不就是把所有f(c)都自减1么，那么如果我们把所有的f(c)都存成相对于一个变量的差值，每次只要改变这一个变量不就可以实现对所有count的减一操作了么?  但是这样还是没有完全解决问题，因为我们还有另外的操作，就是如果f(c)归零，要将该元素删除。要做到这一点，似乎还是得以此扫描候选表中的f(c)。要解决这个问题也很容易，只要把f(c)相同的元素归类到一起形成一个链表，然后按照f(c)的递增顺序将链表串起来就行了。每次只要检测最小的f(c)是否归零，如果归零，那么就把整个链表删掉。

图1：改进后的数据结构

基本的思想就是这样了，先来看最终的数据结构吧。如图1所示，利用hash表，我们可以将各元素一一对应到中间双向链表中的结点，每个结点存取相应元素的出现频率。而处于同一双向链表中的结点频率数相同。这里的双向链表实际上就起到我们上文提到的候选表的作用。最左侧的单向链表用于将各个双向链表按照频率从低到高的顺序串在一起。其中，头结点中存储着真正的频率值 (如图中的3，我们在下文中称之为base)，其他结点皆存储相对其前驱结点的频率差值 (如图中所示的+3, +1)。理所当然的，base值只能为正。同时，每个单链表的结点也作为双向链表的头结点，维护相应双向链表的长度，我们还需要另外维护一个变量total表示当前处于双向链表中的元素个数，也就是候选表的大小。空间复杂度不难分析出来，是。

结合这个数据结构，再来把上面的操作重新分析一下吧。其实我们需要的只有3种操作: 查找当前元素所在的结点，插入新结点，已有结点频率+1，所有已有结点频率-1并删除所有频率降为0的结点，下面我们分别看一下时间复杂度复杂度。

• 查找: O(1) 借助hash表，我们可以在O(1)时间内找到当前元素A[i]所在的结点，进而得知其频率。
• 插入新结点: O(1) 如果没有找到该结点，我们首先需要判断候选表是否已满，如果未满total<K，则需要将其插入到频率值为1的双向链表中。我们通过检测base可以判断该链表是否存在。有的话则直接插入，否则则为单链表新建一个头结点指向一个新的双向链表。当然同时也要更新hash表，以及单链表原头结点的数值 (自减1，变成相对值)。
• 频率自增1: O(1) 如果找到该结点，则需要将其频率自增1。这个操作需要先将其从当前所在的双向链表中摘下来 (O(1) 时间)，插入到f(c)+1所属的链表中。由于双向链表中每个结点我们都额外维护了指向表头的指针，所以我们可以在常量时间内找到其后继双线链表的表头。但注意这个表头未必合适。我们还需要查看其中维护的频率差值，如果为1则直接插入其中；否则的话则建立一个新结点，指向一个新的双向链表。同时也要把这个新结点插入到单链表中，更新其后继结点的差值。当然，链表长度也要进行相应的更新。由于我们采用了双向链表，所以删除和插入新结点都只需要常数时间开销; 同时，对于单链表来说，在当前结点之后插入新结点也只需要常数时间。总体来说，此步骤只需O(1)时间。
• 所有频率自减1：O(1)并删除所有频率归零的结点: 由于双向链表是按照频率由低到高依次排列的，仅有第一个链表的频率可能降为0，因此我们只需要检查其频率，也就是base就可以了。如果base为1，那么直接删除该头结点，和其指向的双向链表；否则的话，base自减1就可以了。因为后继结点存储的都是差值，并不需要一一更新。容易看出，这一步步骤也只需O(1)的时间。

现在基本上是大功告成了，我们通过几个简单数据结构的组合，把每个步骤的时间复杂度从平摊的O(1)优化到了严格的O(1)。不过确实好累。。。其实对于这个问题，还可以继续做下去。比如说，是否存在线性时间的确定性online算法呢? 比如说，输入不是静态的序列，而是stream，也就是没有办法进行二次扫描。那么是否存在线性时间的online算法，来确定地找出iceberg query的结果呢? 说实话这部分内容我还没有深入的了解。目前只知道线性时间带有false positive结果的算法，且如果要做到online的话，至少需要[latex]n\log \frac{N}{n}[/latex]的空间。另外，在这篇论文中，介绍了一种基于概率的方法，不过我没有仔细看 (惭愧啊。。。) 不过有点题外话就是，虽然这篇论文用了跟Karp老爷子一样的算法，但是并没有引用其论文，不知道是怎么个情况。。