|
>学习工控知识，就来工控小新
农历十一月二十五日 2024/1/ 6
往期推荐
2024年1月4日，每日花费一分钟练习C语言
2024年1月5日，每日花费一分钟练习C语言
每
日
一
练
/ Daily Exercises
题目：
寻找峰值
峰值元素是指其值严格大于左右相邻值的元素
给你一个整数数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰
值所在位置即可。
你可以假设nums[-1] = nums[n]= -
你必须实现时间复杂度为 0(logn)的算法来解决此问题。
题目分析
为了实现一个对数时间的算法，我们可以考虑使用二分查找的思想。二分查找是一种在有序数组中查找目标值的算法，它的基本思想是，每次比较数组的中间元素和目标值，如果相等则返回，如果不等则根据大小关系，舍弃一半的数组，继续在剩下的一半数组中查找，直到找到目标值或数组为空。
我们可以将这个思想应用到寻找峰值元素的问题上，但是有一些不同之处。首先，我们不是在有序数组中查找目标值，而是在无序数组中查找峰值元素。其次，我们不是比较数组的中间元素和目标值，而是比较数组的中间元素和其左右相邻元素。最后，我们不是根据大小关系，舍弃一半的数组，而是根据峰值的定义，舍弃一侧的数组，继续在另一侧的数组中查找。
具体来说，我们可以定义一个函数findPeak，它接受一个数组nums和两个整数left和right，表示要查找的数组的左右边界。我们可以假设left和right都是有效的索引，且left<= right。函数的返回值是一个峰值元素的索引，如果不存在则返回-1。
程序展示
如果left > right，说明数组为空，没有峰值元素，返回-1。
- 如果left ==right，说明数组只有一个元素，它就是峰值元素，返回left。
- 否则，计算数组的中间索引mid =(left + right) / 2，比较nums[mid]和nums[mid + 1]的大小关系。
- 如果nums[mid] > nums[mid +1]，说明mid处于一个下降的区间，那么峰值元素可能在mid的左侧，或者就是mid本身，所以我们可以在[left,mid]的区间中继续查找，即返回findPeak(nums, left, mid)的结果。
- 如果nums[mid] < nums[mid +1]，说明mid处于一个上升的区间，那么峰值元素可能在mid的右侧，所以我们可以在[mid + 1,right]的区间中继续查找，即返回findPeak(nums, mid + 1, right)的结果。
- 如果nums[mid] == nums[mid +1]，说明mid处于一个平坦的区间，那么峰值元素可能在mid的两侧，或者不存在，所以我们可以在任意一侧的区间中继续查找，比如返回findPeak(nums,left, mid)的结果。
这个算法的时间复杂度是O(logn)，因为每次我们都会舍弃一半的数组，所以最多需要进行log n次查找。空间复杂度是O(logn)，因为我们使用了递归，所以需要额外的栈空间来存储递归调用的信息。
#include<stdio.h>// 寻找峰值元素的函数，接受一个数组nums，一个数组的长度n，和两个整数left和right，表示要查找的数组的左右边界// 返回一个峰值元素的索引，如果不存在则返回-1int findPeak(int nums[], int n, int left, int right) { // 如果left > right，说明数组为空，没有峰值元素，返回-1 if (left > right) { return -1; } // 如果left == right，说明数组只有一个元素，它就是峰值元素，返回left if (left == right) { return left; } // 否则，计算数组的中间索引mid int mid = (left + right) / 2; // 比较nums[mid]和nums[mid + 1]的大小关系 if (nums[mid] > nums[mid + 1]) { // 如果nums[mid] > nums[mid + 1]，说明mid处于一个下降的区间，那么峰值元素可能在mid的左侧，或者就是mid本身 // 所以我们可以在[left, mid]的区间中继续查找，即返回findPeak(nums, n, left, mid)的结果 return findPeak(nums, n, left, mid); } else if (nums[mid] < nums[mid + 1]) { // 如果nums[mid] < nums[mid + 1]，说明mid处于一个上升的区间，那么峰值元素可能在mid的右侧 // 所以我们可以在[mid + 1, right]的区间中继续查找，即返回findPeak(nums, n, mid + 1, right)的结果 return findPeak(nums, n, mid + 1, right); } else { // 如果nums[mid] == nums[mid + 1]，说明mid处于一个平坦的区间，那么峰值元素可能在mid的两侧，或者不存在 // 所以我们可以在任意一侧的区间中继续查找，比如返回findPeak(nums, n, left, mid)的结果 return findPeak(nums, n, left, mid); }}
// 主函数，测试findPeak函数的功能int main() { // 定义一个测试用的数组nums int nums[] = {1, 2, 1, 3, 5, 7, 4}; // 获取数组的长度n int n = sizeof(nums) / sizeof(nums[0]); // 调用findPeak函数，传入数组nums，数组的长度n，和数组的左右边界0和n - 1 // 将返回值赋给变量peak // 调用findPeak函数，传入数组nums，数组的长度n，和数组的左右边界0和n - 1 // 将返回值赋给变量peak int peak = findPeak(nums, n, 0, n - 1); // 如果peak不等于-1，说明找到了峰值元素，打印其索引和值 if (peak != -1) { printf("The peak element is at index %d, and its value is %d.\n", peak, nums[peak]); } else { // 如果peak等于-1，说明没有找到峰值元素，打印提示信息 printf("There is no peak element in the array.\n"); } // 返回0，表示程序正常结束 return 0;}
程序测试
为了验证我们的程序是否正确，我们可以用一些测试用例来检验。
这就是我用C语言写的寻找峰值元素的程序，它可以在VC6.0的环境下运行。你可以尝试用不同的数组来测试它的功能，看看它是否能正确地找到峰值元素。
源代码获取
#软件下载通道#
我用夸克网盘分享了「20240106」，点击链接即可保存。打开「夸克APP」，无需下载在线播放视频，畅享原画5倍速，支持电视投屏。
链接：https://pan.quark.cn/s/5ccc64bac4e8
(链接和提取码建议复制粘贴，手动输入容易出现错误）
| #支持一下#
分享整理，测试发布不易 如果您方便的话可以帮忙点一下↓↓
谢谢大家！
|
下期题目
C语言题目：二进制求和，给你两个二进制字符串，返回他们的和（用二进制表示）。输入为非空字符串且只包含数字1和0
点赞加关注，学习不迷路
微信公众号｜工控小新
EPLAN电气绘图、TIA博图基础 、CAD、C语言教学、单片机基础、三菱PLC ... 每日持续更新中
发现“分享”和“赞”了吗，戳我看看吧
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
