寻找主要元素

今天写算法作业，遇到了和《数据结构与算法分析—C语言描述》2.19类似的题。分享一下自己的想法。

原题如下：

大小为N的数组A，其主要元素是一个出现次数超过N/2的元素（从而这样的元素最多有一个）。例如数组3,3,4,2,4,4,2,4,4有一个主要元素4，而数组3,3,4,2,4,4,2,4没有主要元素。如果没有主要元素，那么你的程序应该指出来。下面是求解该问题的一个算法的概要：

首先，找出主要元素的一个候选元。这个侯选元是惟一有可能是主要元素的元素。

第二步确定是否该候选元实际上就是主要元素。这正好是对数组的顺序搜索。

为找出数组A的一个候选元，构造第二个数组B。比较A1和A2。如果它们相等，则取其中之一加到数组B中；否则什么也不做。然后比较A3和A4，同样地，如果它们相等，则取其中之一加到B中；否则什么也不做。以该方式继续下去直到读完这个的数组。然后，递归地寻找数组B中的候选元；它也是A的候选元。

b．当N是奇数时，如何处理?
c．该算法的运行时间是多少？

根据上述算法，如果元素个数一直是偶数，假设主要元素存在，那么不断合并，主要元素最终会剩下来，所以只用检验最终剩余的数字；如果没有剩余，那么就不存在主要元素。

这里主要讨论b问，即对奇数的处理。

1. 直接删去最后一个数

乍一想，似乎会有下面的情形出现，多出的1被删除，导致无法找到主要元素。

1 1 2 2 1

但是，换个角度，如果被删去的元素不是主要元素，那么没有任何影响，只用检验最终剩下的数字；如果被删去的是主要元素，有影响的情况仅限于主要元素有k+1个，其他全部都是k个相同的非主要元素。如果是这种情况，那么遗留下来的必然是两个元素，只要对这两个元素分别检验就行了，且检验总耗时为O(n)。

2. 直接保留最后一个数

和上面一种情况类似，如果保留的是主要元素，那么没有任何影响，只用检验最终数字；如果保留的是非主要元素，有影响的情况仅限于非主要元素全部都是相同的数字，且仅比主要元素少一个。此时遗留下来的必然是两个元素，只要对这两个元素分别检验就行了，且检验总耗时为O(n)。

3. 及时检验

也就是说如果遇到奇数的情况，就检验最后一个数字是否在当前候选序列中是主要元素。如果是，直接跳出递归，在全局检验该数；否则直接删掉。注意到由于只检查这一个数字，所以耗时也是线性的。

4. 备份法（原书答案中的方法）

如果遇到奇数的情况就直接删掉最后一个数，但同时将删去的数字保留在一个变量里。如果递归到最后数组中仍存在一个数字，那么只用检验该数字；否则，检验最后一个奇数情况删去的数字。正确性的证明和直接删除法类似。

时间复杂度分析：

由于合并本身就会花费线性的时间，所以由T(n)=T(n/2)+O(n)可知，递归用时T(n)=O(n)，加上最后检验的O(n)，四种情况的总耗时均为O(n)。

综合比较

算法	递归终止条件	耗时
直接删去法	剩余元素小于等于2	O(n)
直接保留法	剩余元素小于等于2	O(n)
及时检验法	剩余元素小于等于1	O(n)
备份法	剩余元素小于等于1	O(n)