本文主要是介绍2013 候选主元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
已知一个整数序列A=(a0，a1，…，an-1)，其中0≤ai＜n(0≤i＜n)。若存在ap1=ap2=…=apm=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。要求：给出算法的基本设计思想。
题意：找出出现次数大于n/2次的数。
算法描述：
遍历数组，选取第一个数为候选主元素c，初始化出现次数k为1。如果下一个数也是c，则k++；如果不是c，则k--。 如果k=0，选取新的数为c。再遍历一次数组查看c出现次数是否大于n/2次。
如果存在大于n/2的数，则该算法一定能找到。如果不存在出现次数大于n/2的数，找到的就不是现次数大于n/2的数。故需要第二次遍历检验。
时间复杂度O(n)，空间复杂度O（1）。
int find_main(int a[],int n){int c=a[0];int k=1;for(int i=1;i<n;i++){if(a[i]==c){k++;}else{k--;if(k==0){c=a[i];k=1;}}}k=0;for(int i=0;i<n;i++){if(a[i]==c) k++;}return (k>n/2)?c:-1;
} 也可使用一个辅助数组标记出现次数，再遍历看是否存在出现次数大于n/2的数，时间复杂度O(n)，空间复杂度O（n），这样最高可得十分，比上述算法少一分。
这篇关于2013 候选主元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
