首页 > 代码库 > 寻找主元素
寻找主元素
主元素这个问题，有个nlogn的算法，但是还有比它更快的，有O(n)的算法，基本思想是，从头到尾遍历，先将第一个元素保存到一个变量中，然后依次往后遍历，每遍历到与它的值相同的元素时，就要将它的个数+1， 不同时-1， 这样是因为如果存在主元素，那么主元素的个数一定是大于n/2的，所以最后这样抵消下来剩下的一定是主元素，如果判断它不存在呢，就需要再遍历一遍，看最后找到的这个是不是主元素，其中有个细节就是当那个保存的个数减到0的时候怎么办，如果减到零，就让它等于当前遍历到的这个元素，代码如下，
1 #include <stdio.h> 2 const int N = 1000; 3 int a[N]; 4 5 int main() 6 { 7 int n; 8 while (~scanf("%d", &n)) 9 {10 for (int i = 0; i < n; i++)11 scanf("%d", &a[i]);12 13 int cur_value = http://www.mamicode.com/a[0], cur_count = 1;/*cur_value用来保存当前容器中的值，14 cur_count表示当前值为cur_value的个数 */15 for (int i = 1; i < n; i++)16 {17 if (cur_count == 0)//如果抵消完，将它的值改成当前遍历到元素的值 18 {19 cur_count = 1;20 cur_value =http://www.mamicode.com/ a[i];21 }22 else23 {24 if (cur_value =http://www.mamicode.com/= a[i])//如果相等，就++ 25 {26 cur_count++;27 }28 else//不等，就-- 29 cur_count--;30 }31 }32 int cnt = 0;33 for (int i = 0; i < n; i++)//判断是否存在主元素 34 if (cur_value =http://www.mamicode.com/= a[i])35 cnt++;36 if (cnt > n / 2)37 printf("%d\n", cur_value);38 else39 puts("NO");40 }41 42 43 return 0;44 }
寻找主元素
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。