本文主要是介绍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语言练习题 寻找峰值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!