C语言练习题 寻找峰值

2024-08-22 22:28
文章标签 语言 练习题 寻找 峰值

本文主要是介绍C语言练习题 寻找峰值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个所在位置即可。

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = −∞

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

数据范围:

1≤  nums.length ≤ 2×10^5 

−2^31<= nums[i] <= 2^31 − 1

分析:

1、数组首元素前一位和数组尾元素后一位都是负无穷。

2、题目给出条件3.对于所有有效的 i 都有 nums[i] != nums[i + 1],即数组中所有相邻两数不相等。

3、题目给的数据范围是 int 取值范围,做题时使用 int 数据即可。

则数组首元素大于自身前一位数值,末端元素大于自身后一位数值。

根据题目信息,可以分为以下情况

a、数组只有一个元素,则它大于自己前面的负无穷,同时又大于后面的负无穷,峰值为其本身。

b、数组有多个元素,其首元素大于第二个元素,是一个峰值。

c、数组有多个元素,其尾元素大于倒数第二个元素,是一个峰值。

d、数组有多个元素,且其首、尾元素均不是峰值。

遍历查找:

//遍历法
int find(int* nums, int numsLen)	//nums 是数组名,numsLen 是数组长度
{int i = 0;if (numsLen == 1)	//如果数组只有一个元素,则峰值为其本身,返回 0 。return 0;if (nums[0] > nums[1])	//如果数组首元素大于第二个元素,则为一个峰值,返回 0 。return 0;if (nums[numsLen - 1] > nums[numsLen - 2]) //如果数组尾元素大于倒数第二个元素,则为一个峰值,返回为元素符号位。return numsLen - 1;for (i = 0; i < numsLen; i++)	//遍历数组每个元素,找到峰值,返回其符号位。{if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1])return i;}
}

遍历查找比较简单,但数据量大的时候,可能出现耗时较高的情况,下面采用二分法查找。

峰值的两侧分别为上升和下降,则只要区间的左边界是上升的,右边界是下降的,那么其中间必定存在峰值。使用二分法查找峰值时,主要是判断二分之后哪边一定存在峰值。

按照题意,数组左边是无穷小,即一定是上升沿;右边也是无穷小,则一定是下降沿。上升沿和下降沿中间一定存在峰值。取其中间值判断,若中间值所在位置为上升阶段,则其和右边下降沿中间一定有峰值,可以将左边界置于中间位置,重新查找;若中间值为下降阶段,则其和左边上升沿中间一定有峰值,可以将右边界置于中间位置,重新查找。

二分之后,新的区间如起始一样,其左边为上升沿,右边为下降沿,取其中间值判断,思路与初始相同。

如此循环下去,当中间值左边是上升沿(中间值大于前一位元素),右边是下降沿时(中间值大于后一位元素),则中间值为峰值。

二分法查找代码演示:
 

//二分法查找
int find(int* nums, int numsLen)	//nums 是数组名,numsLen 是数组长度
{int left = 0;					//区间左边界定义为数组首元素符号位 0 。int right = numsLen - 1;		//区间右边界定义为数组为元素符号位 numsLen - 1 。if (numsLen == 1)				//如果数组只有一个元素,则峰值为其本身,返回 0 。return 0;if (nums[left] > nums[left +1 ])	//如果数组首元素大于第二个元素,则为一个峰值,返回 0 。return left;if (nums[right] > nums[right - 1])	//如果数组尾元素大于倒数第二个元素,则为一个峰值,返回为元素符号位。return right;while(left < right)				//区间左边界小于右边界则继续循环查找{int mid = (left + right) / 2;	//区间中段定义为 左边界与右边界中间数值//如果中间元素小于其后面一个元素,那么在其右侧一定存在峰值if (nums[mid] < nums[mid + 1])	{left = mid;		//将mid 赋值给 左边界}else           //如果中间元素大于其后面一个元素,那么在自身及其左侧一定存在峰值{if (nums[mid] > nums[mid - 1])	//如果中间元素同时大于其前面一个元素,那么其为峰值return mid;			//返回中间元素的符号位else		//如果中间元素小于其前面一个元素,那么在其左侧一定存在峰值right = mid;	//将mid 复制给 右边界}}
}

这篇关于C语言练习题 寻找峰值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道(channel)操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1:监听多个通道示例 2:带

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点