highlight: a11y-dark
41题
王道解析：
算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num 。然后重新计数，确认Num是否是主元素。算法可分为以下两步：
-
选取候选的主元素：依次扫描所给数组中的每个整数， 将第一个遇到的整数Num保存到c中， 记录Num的出现次数为1; 若遇到的下一个整数仍等于Num, 则计数加1, 否则计数减1; 当计数减到0时， 将遇到的下一个整数保存到c中，计数重新记为1, 开始新一轮计数，即从当前位置开始重复上述过程， 直到扫描完全部数组元素。
-
判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于n/2, 则为主元素；否则， 序列中不存在主元素。
int Majority(int A[], int n) {
int i, c, count = 1; //c用来保存候选主元素，count用来计数
c = A[0]; //设置A[O]为候选主元素
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; //不存在主元素
}
最优解：
int find(int A[],int n){
QuickSort(A,0,n-1);//快速排序O(nlog2n)
int k,max=0,count=1;
for(int i=0;i<n-1;++i){
if(A[i+1]==A[i]){
count++;
}else{
if(count>max){
max=count;
k=A[i];
}
count=1;
}
}
if(max>n/2)
return k;
else
return -1;
}
暴力解1
int fun ( int A[], int n ) {
int* B = (int*) malloc( sizeof (int) * n ) ;
for ( int i = 0; i < n; ++i )
B[i] = 0 ;
int i, k ;
int max = 0 ;
for ( i = 0; i < n; ++i )
if ( A[i] > 0 && A[i] <= n )
B[A[i] - 1]++ ;
for ( i = 0; i < n; ++i )
if ( B[i] > max ) {
max = B[i] ;
k = i ;
}
if ( max > n / 2 )
return k + 1 ;
else
return -1 ;
}
暴力解2：双层循环
- 选择数组的每一个元素i
- 统计i在整个数组出现的次数
- 如果大于n/2则返回
题目要求我们查找是否存在主元素，那可以直接定义找到为1，没找到为0，并写好注释。既然要找某个数是否满足主元素的性质，那就每个数去检查是否为主元素，要检查每个元素，则需要遍历。
int majority(int A[], n) {
int m;
//遍历每一个元素
for (int i = 0; i < n; i++) {
//由于每次遍历的元素 都是从0开始统计出现的次数m=0;
for (int j = 0; j < n; j++)
if (A[i] == A[j])
m++;
if (m > n / 2) {
//找到了主元素
return A[m];
}
}
//未找到主元素
return -1;
}
