首页 > 代码库 > C程序设计的抽象思维-算法分析-大多数元素
C程序设计的抽象思维-算法分析-大多数元素
【问题】
请编写以下函数 int MajorityElement(int array[],int n);
该函数返回数组array中的多数元素。多数元素是指在占绝对多数（至少51%）的一个值。如果多数元素不存在，那么返回常量NoMajorityElement,该函数必须满足下面的条件：1. 必须以O(N)时间运行。
2. 必须使用O（1）的附加空间。换句话说，可用个别的临时变量，而不可以使用任何的临时数组。并且不能使用递归解决，这是因为随着递归层数加深，会需要空间来存储栈帧。
3. 不能改变数组中的任何元素的值。
【代码】
#include <stdio.h>
void MajorityElement(int array[], int n)
{
int majority, i, count;
majority = array[0];
count = 1;
for(i = 1; i < n; i++){
if(majority != array[i]){
if(count == 0){
majority = array[i];
count++;
}else{
count--;
}
}else{
count++;
}
}
if(count > 0)
printf("MajorityElement: %d\n", majority);
else
printf("NoMajorityElement\n");
}
main()
{
int array[5] = {1, 2, 1, 2, 3};
MajorityElement(array, 5);
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。