数据结构
2013-41
已知一个整数序列 A=(a0,a1,…,an-1)，其中 0≤ ai<n（0≤ i<n）。若存在 ap_1=ap_2=…=ap_m=x 且 m>n/2（0≤ pk<n，1≤ k≤ m），则称 x 为 A 的主元素。例如 A=(0,5,5,3,5,7,5,5)，则5为主元素；又如 A=(0,5,5,3,5,1,5,7)，则 A 中没有主元素。假设 A 中的 n 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 A 的主元素。若存在主元素，则输出该元素；否则输出 -1。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用 C、C++或 Java 语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。
答案
（1）算法的基本设计思想：采用摩尔投票算法。首先遍历数组，通过计数方式找出一个可能的候选主元素：遇到相同元素计数加一，不同则计数减一，计数为零时更换候选元素。然后再次遍历数组，统计候选元素出现次数，若超过n/2则输出该元素，否则输出-1。
（2）算法实现（C语言）：
int Majority(int A[], int n) {
int i, c, count = 1; // c用来保存候选主元素，count用来计数
c = A[0]; // 设置A[0]为候选主元素
for (i = 1; i < n; i++) // 查找候选主元素
if (A[i] == c)
count++; // 对A中的候选主元素计数
else {
if (count > 0)
count--; // 处理不是候选主元素的情况
else {
c = A[i]; // 更换候选主元素，重新计数
count = 1;
}
}
if (count > 0)
for (i = count = 0; i < n; i++) // 统计候选主元素的实际出现次数
if (A[i] == c)
count++;
if (count > n / 2) return c; // 确认候选主元素
else return -1; // 不存在主元素
}（3）时间复杂度和空间复杂度：
- 时间复杂度：O(n)，两次线性遍历数组。
- 空间复杂度：O(1)，仅使用常数额外变量。