一：题目

主元素是指：一个数在数组中出现的次数超过数组长度的一半，那么这个数就是数组元素的主元素。例如：{0,5,5,3,4,5,5,5,5,9}这里面元素5有6个超过了一半，所以就是主元素 使用一种高效率的方法找出数组A的主元素，若有，则输出该元素，否则返回-1

二：思路

这里我们使用计数器的方法来标记数据元素，将第一个元素设置为候补主元素，计数为1，若是下一个元素还是相同的数，计数+1，若是不同，计数-1，当计数为0，则换下一个元素来做候补主元素，计数变1以此循环。 若是数组存在一个真正的主元素，那么该元素的计数一定是一个大于0的数

第一步：选取2作为候补主元素，计数为1

 

第二步：向后移动，发现数据不同，计数减一，为0，此时变化候补主元素为3，计数变1

第三步：向后移动，发现数据相同，计数加一，为2 

第四步：向后移动，发现数据相同，计数加一，为3

第五步：向后移动，发现数据和候补主元素不同，计数减一，为2

第六步：向后移动，发现数据和候补主元素相同，计数加一，为3

第七步：向后移动，发现数据和候补主元素不同，计数减一，为2

第八步：向后移动，发现数据和候补主元素相同，计数加一，为3

第九步：向后移动，发现数据和候补主元素相同，计数加一，为4

 

第十步：向后移动，发现数据和候补主元素不同，计数减一，为3

遍历结束！此时候补主元素为3，计数君为正数，但是我们不能确定是否一定是主元素，所以我们应该循环一遍对该元素进行比较计数，若是计数超过一半，那么这个就是主元素！

三：算法实现

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> int majority(int A[], int n) { int i=1, count=1; ////计数用 int maj = A[0]; for (i = 0; i < n;i++) { if (A[i] == maj) count++; else { if (count > 0) count--; else { maj = A[i]; count = 1; } } } if (count>0) //找到一个最有可能是主元素的值 { //循环计数验证 count = 0; for (i = 0; i < n; i++) if (A[i] == maj) count++; } if (count > n / 2) return maj; return -1; } int main() { int A[10] = { 2, 3, 3, 3, 9, 3, 7, 3, 3, 4 }; int ret; ret = majority(A,10); printf("%d", ret); system("pause"); return 0; }

 

转载于:https://www.cnblogs.com/ssyfj/p/9569087.html

相关资源：C 实现找出数组中的主元素