做it的在哪个网站找工作,在俄罗斯做网站需要多少卢布,wordpress怎么设置友情链接,百度网站前面的图片文章目录 2013年408应用题41方法一方法二 看到的社区的一个知识总结#xff0c;这里记录一下。 知识点汇总
2013年408应用题41 解决方法#xff1a;
方法一
#xff08;1#xff09;算法思想
算法的策略是从前向后扫描数组元素#xff0c;标记出一个可能成为主元素的元… 文章目录 2013年408应用题41方法一方法二 看到的社区的一个知识总结这里记录一下。 知识点汇总
2013年408应用题41 解决方法
方法一
1算法思想
算法的策略是从前向后扫描数组元素标记出一个可能成为主元素的元素Num。然后重新计数确认Num是否是主元素。算法可分为以下两步:
①选取候选的主元素:依次扫描所给数组中的每个整数将第一个遇到的整数Num保存到c中记录Num的出现次数为1;若遇到的下一个整数仍等于Num,则计数加1,否则计数减1;当计数减到0时将遇到的下一个整数保存到c中计数重新记为1,开始新一轮计数即从当前位置开始重复上述过程直到扫描完全部数组元素。
②判断c中元素是否是真正的主元素:再次扫描该数组统计C中元素出现的次数若大于n/2则为主元素;否则序列中不存在主元素。
2代码如下
#includestdio.h
#includestdlib.hint Majority(int A[],int n){int i,c,count 1;//c用来保存候选主元素count用来计数cA[0];//设置A[0]为候选主元素for(i1;in;i){if(A[i]c) count;//对A中的候选主元素进行排序else if(count0)count--;else {cA[i];count1;}}if(count0){//判断c中元素是否是真正的主元素for(icount0;in;i)if(A[i]c)count;}if(countn/2)return c;else return -1;
}该算法的时间复杂度为On空间复杂度为O1。
与算法一致且回答正确时间空间各一分
方法二
采用计数排序的思想
申请一个辅助计数数组如果数字出现一次则在辅助技术数组中加一返回查看辅助计数数组如果出现次数大于n/2则返回元素max否则返回-1
#includestdio.h
#includestdlib.hint Majority(int A[],int n){int k,*p,max;p(int *)malloc(sizeof(int)*n);//申请辅助计数数组for(k0;kn;k){p[k]0;}max0;for(k0;kn;k){p[A[k]];if(p[A[k]]p[max])maxA[k];}if(p[max]n/2)return max;else return -1;}
