王道p18 第12题假设 A中的 n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出A的主元素。若存在主元素,则输出该元素:否则输出-1

本文主要是介绍王道p18 第12题假设 A中的 n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出A的主元素。若存在主元素,则输出该元素:否则输出-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(count>0)//统计候选主元素的实际出现次数for (i = 0, count = 0; i < n; i++){if (a[i] == c)count++;}if (count > n / 2)//确认候选主元素return c;else//不存在主元素return -1;
}

完整测试代码

#include<stdio.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(count>0)//统计候选主元素的实际出现次数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}测试结果为

这篇关于王道p18 第12题假设 A中的 n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出A的主元素。若存在主元素,则输出该元素:否则输出-1的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/368485

相关文章

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

基于Python实现高效PPT转图片工具

《基于Python实现高效PPT转图片工具》在日常工作中,PPT是我们常用的演示工具,但有时候我们需要将PPT的内容提取为图片格式以便于展示或保存,所以本文将用Python实现PPT转PNG工具,希望... 目录1. 概述2. 功能使用2.1 安装依赖2.2 使用步骤2.3 代码实现2.4 GUI界面3.效

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,:本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点:适用场景:二、JPEG质量参数压缩关键技术:压缩效果对比

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis