首页 > 代码库 > 候选人算法
候选人算法
现在有一个整数数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数
#include <stdio.h>int main(int argc, char **argv){ int i, candidate, vote; int a[10]={1,2,3,1,2,1,1,6,1,1}; candidate = 1<<31; vote = 0; for (i = 0; i < 10; i++) { if (a[i] != candidate) { if (vote == 0) { /* 废掉candidate, 把a[i]作为新的候选人 */ candidate = a[i]; vote = 1; } else { /* 候选人的票减1 */ vote--; } } else { /* 候选人的票加1 */ vote++; } } // 最后剩下的候选人即为出现次数超过一半的数 printf("candidate = %d, vote = %d\n", candidate, vote); return 0;}
候选人算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。