王道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

相关文章

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

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

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

python多种数据类型输出为Excel文件

《python多种数据类型输出为Excel文件》本文主要介绍了将Python中的列表、元组、字典和集合等数据类型输出到Excel文件中,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参... 目录一.列表List二.字典dict三.集合set四.元组tuplepython中的列表、元组、字典