现在有一个整数数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数。
算法:充分利用出现次数超过一半这个特点,使用两个变量candidate和vote,分别代表候选人和票数,遍历数组
按如下方式投票和更换候选人:
若当前数与候选人一样,则把候选人的票数加1
若当前数与候选人不一样, 则把它的票数减1,如果减掉后票数小于0,则把候选人踢掉,用当前数作为新的候选人
最后剩下的候选人就是出现次数超过一半的数。
算法的正确性证明: 数组中,数值相同的数都会投赞成票,数值不同的都会投反对票,有一个数出现的次数超过一半,
其它数得到的反对票必然大于一半,所以其它数中,任何一个得票都会小于0,遭到淘汰。剩下来的只能是超过一半
的那个数。
#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;
}
分享到:
相关推荐
算法课本的题目,要求复杂度是(nlgn)。
26、 设计一个O(n2)时间的算法,找出由n个数组成的序列的最长的单调递增子序列。 27、 旅游预算问题。一个旅行社需要估算乘汽车从某城市到另一城市的最小费用,沿路有若干加油站,每个加油站收费不一定相同。旅游...
8. 一个算法具有 5个特性: (1)有穷性 、 (2)确定性 、 (3)可行性 ,有零个或多个输入、有一个或多个输出。 《数据结构 1800题》 9.已知如下程序段 FOR i:= n DOWNTO 1 DO {语句 1} BEGIN x:=x+1;...
判断一个整数P(P>1)是否为素数最简单的方法就是看是否存在一个素数a(a(P))是P的约数,如果不存在,该数就为素数,由于在此题中1,n,所以要判断的数P不会超过100000000,sqrt(p),因此,为了加快速度,我们可以用筛选...
数 据 结 构 习 题 习题一 1.1 书写函数,实现求任一整数数组中的最小值。 1.2书写实现如下功能的函数声明:已知一个含有n个元素的数组,从第i个元素开始移走 k个元素。 1.3用typedef定义学生成绩记录的类型,并书写...
程序4 约瑟夫环问题:任给正整数N和K,按下述方法可以得到1,2,…,n的一个置换:将数 字1,2,…,n环形排列,按顺时针方向自1开始报数,报到K时输出该位置上的数字,并 使其出列,然后从它顺时针方向的下一个...
2、 已知a[n]为整数数组,试写出实现下列运算的递归代码(C或C++代码均可): 要求: a. 求数组中的最大整数; b. 求n个数的和; c. 利用堆栈类,将本题a和b的代码改成非递归的方式。 实验报告...
已知带头结点的动态单链表L中的结点是按整数值递增排序的,试写一算法将值为的结点插入到表L中,使L仍然有序。要求算法的时间复杂度为 O(),空间复杂度为 O(1)。2、设计一算法,逆置带头结点的动态链表L。要求利用原...
1.6.3. 输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数 位于数组的后半部分 ...........................................................130 1.6.4. 给定链表的头指针和一个...
h) 一个有10个指针的数组,该指针指向一个函数,该函数有一个整型参数并返回一个整型数( An array of ten pointers to functions that take an integer argument and return an integer ) 答案是: a) int a; //...
numbers:给定一个数集合和一个数,已知集合中有两个数的和是给定数,求这两个加数的index 方法1:暴力,n^2时间复杂度,不推荐 方法2:快速排序nlogn。按集合里数的两倍与target的大小关系对分。对每一个第一部分的...