题目

已知一个整数序列A=(ao, a, .. an-1), 其中0≤a<n (0≤i<n)。 若存在a(p1)=a(p2)=...=a(pm)=x且m>n/2 (0≤p(k)<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。

分析

第一种思路就是暴力破解，双层循环，时间复杂度为O(n^2)。

第二种思路如下：

①选取候选的主元素。依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1;若遇到的下一个整数仍等于Num,则计数加1,否则计数减1:当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1,开始新一轮计数， 即从当前位置开始重复上述过程，直到扫描完全部数组元素。

②判断c中元素是否是真正的主元素。再次扫描该数组，统计c中元素出现的次数，若大于n2，则为主元素;否则，序列中不存在主元素。

代码

第一种思路的核心代码如下：

/* 找出主元素 */
/* A[]指的是顺序表A，n指的是A顺序表的长度 */ 
void findEle(int A[],int n){int ele=0;// 将主元素的值设置为0，作为一个判断标志，如果是0则没有主元素，否则有主元素 for(int i=0;i<n;i++){// 循环A顺序表的所有元素 int count=0;// 计数器，记录A顺序表中每个元素的出现次数 for(int j=0;j<n;j++){// 再次循环A顺序表的所有元素，来统计每个元素的出现次数 if(A[i]==A[j]){count++;// 统计每个元素的出现次数 }}if(count>n/2){// 当满足这个条件时，该元素就是主元素 ele=A[i];// 然后将主元素的值赋给ele }}if(ele!=0){// 判断是否存在主元素 printf("%d",ele);// 如果有则输出主元素的值 }else{printf("-1");// 否则输出-1 }
}

完整代码：

#include<stdio.h>/* 打印顺序表 */
void print(int L[],int m) {printf("\n");for(int i=0; i<m; i++) {printf("%d\t",L[i]);}printf("\n");
}/* 找出主元素 */
/* A[]指的是顺序表A，n指的是A顺序表的长度 */
void findEle(int A[],int n) {int ele=0;// 将主元素的值设置为0，作为一个判断标志，如果是0则没有主元素，否则有主元素for(int i=0; i<n; i++) { // 循环A顺序表的所有元素int count=0;// 计数器，记录A顺序表中每个元素的出现次数for(int j=0; j<n; j++) { // 再次循环A顺序表的所有元素，来统计每个元素的出现次数if(A[i]==A[j]) {count++;// 统计每个元素的出现次数}}if(count>n/2) { // 当满足这个条件时，该元素就是主元素ele=A[i];// 然后将主元素的值赋给ele}}if(ele!=0) { // 判断是否存在主元素printf("%d",ele);// 如果有则输出主元素的值} else {printf("-1");// 否则输出-1}
}int main() {int L1[]= {0,5,5,3,5,7,5,5};int l1=8;print(L1,l1);// 打印顺序表findEle(L1,l1);return 0;
}

第二种思路的代码如下：

void majority(int A[],int n){int i,c,count=1;// c用来保存候选元素，count用来计数c=A[0];// 设置A[0]为候选主元素 for(int i=0;i<n;i++){if(A[i]==c){count++;// 对A中的候选主元素计数 }else{if(count>0){// 处理不是候选主元素的情况 count--;}else{c=A[i];count=1;}}} if(coutn>0){for(int i=count=0;i<n;i++){// 统计候选元素的实际出现次数if(A[i]==c){count++;} }}if(count>n/2){return c;// 确认候选主元素 }else{return -1;}
}