网站制作公司要文化建设费,深圳住房和建设局网站哪里预约,做暧嗳xo小视频网站,网络推广公司收费标准视频讲解在#xff1a;#x1f447;
p18 第12题 c语言实现王道数据结构课后习题_哔哩哔哩_bilibili
从前向后扫描数组元素#xff0c;标记出一个可能成为主元素的元素 Num。然后重新计数#xff0c;确认 Num 是否是主元素。
我们可分为以下两步: 1.选取候选的主元素。依… 视频讲解在
p18 第12题 c语言实现王道数据结构课后习题_哔哩哔哩_bilibili
从前向后扫描数组元素标记出一个可能成为主元素的元素 Num。然后重新计数确认 Num 是否是主元素。
我们可分为以下两步: 1.选取候选的主元素。依次扫描所给数组中的每个整数将第一个遇到的整数 Num 保存到c中记录 Num 的出现次数为 1:若遇到的下一个整数仍等于 Num则计数加 否则计数减 1;当计数减到 0时将遇到的下一个整数保存到c 中计数重新记为 1开始新一轮计数即从当前位置开始重复上述过程直到扫描完全部数组元素。
2.判断 c中元素是否是真正的主元素。再次扫描该数组统计 c 中元素出现的次数若大于n/2则为主元素;否则序列中不存在主元素。
让我们来看一下代码该如何实现
int majority(int a[], int n)
{int i 0;int c 0;//c用来保存候选主元素count用来计数int count 1;c a[0];//设置a[0]为候选主元素for (i 1; i n; i)//查找候选主元素{if (a[i] c)//对a中的候选主元素计数count;elseif (count 0)//处理不是候选主元素的情况count--;else//更换候选主元素重新计数{c a[i];count 1;}}if(count0)//统计候选主元素的实际出现次数for (i 0, count 0; i n; i){if (a[i] c)count;}if (count n / 2)//确认候选主元素return c;else//不存在主元素return -1;
}
完整测试代码
#includestdio.h
int a[8] { 0,5,5,3,5,7,5,5};
int n 8;
int majority(int a[], int n)
{int i 0;int c 0;//c用来保存候选主元素count用来计数int count 1;c a[0];//设置a[0]为候选主元素for (i 1; i n; i)//查找候选主元素{if (a[i] c)//对a中的候选主元素计数count;elseif (count 0)//处理不是候选主元素的情况count--;else//更换候选主元素重新计数{c a[i];count 1;}}if(count0)//统计候选主元素的实际出现次数for (i 0, count 0; i n; i){if (a[i] c)count;}if (count n / 2)//确认候选主元素return c;else//不存在主元素return -1;
}
int main()
{int ret majority(a, n);if (ret ! -1)printf(中位数为%d, ret);elseprintf(未找到);return 0;
}
用a[8]{0,5,5,3,5,1,5,7 }测试结果为 用a[8] { 0,5,5,3,5,7,5,5}测试结果为
