devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

c++_leetcode_寻找峰值_使用c++寻找一组数据的所有波峰位置

作者：笔触狂放9 | 2024-04-29 21:30:27

赞

踩

使用c++寻找一组数据的所有波峰位置

目录

一、寻找峰值的示例

二、官方实现代码及解释

1、官方测试结果：

2、代码解释：

3、解题思路：

三、我的暴力解决

1、测试一：

2、测试二：

3、最终“暴力求解”代码：

4、官网提交测试通过：

 5、解题思路：

四、c++函数max_element（）解决

1、函数使用介绍：

2、max_element（） 峰值寻找完整代码：

一、寻找峰值的示例

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

提示：

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1
  • 对于所有有效的 i 都有 nums[i] != nums[i + 1]

二、官方实现代码及解释

1、官方测试结果：

2、代码解释：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {

        //1、准备工作：获得nums、生成随机索引值

        //随机索引值在一定概率上可以快速得到峰值，最好情况是刚好随机到峰值数的索引，最差情况是刚好随机到距离峰值最远的元素
        int n = nums.size();  //得到nums数据长度
        int idx = rand() % n;  //随机生成0~n-1的索引idx值

         //2、设计函数get，输入i，得到数组对(0/1, nums[i])

        // 辅助函数，输入下标 i，返回一个二元组 (0/1, nums[i])
        // 方便处理 nums[-1] 以及 nums[n] 的边界情况

        auto get  = [&](int i)->pair<int,int>{
            if(i==-1||i==n)
            {
                return{0,0};
            }
            return {1,nums[i]};
        };

详细解释lambda表达式：

  • get是函数名
  • [&]是所有变量以引用捕获的方式传入到表达式中，也就是i传入后可访问、修改
  • (int i)是参数列表，这里参数是整型
  • -> pair<int,int>是返回值类型为pair<int,int>,定义为两个int型的数据对
  • {} 里面是函数体，此处返回(0/1, nums[i])，0是超过边界的数对，1是符合边界0~n-1的所有数对

        while(!(get(idx - 1)<get(idx)&&get(idx)>get(idx + 1))){
            if(get(idx)<get(idx+1))
            {
                idx += 1;
            }
            else
            {
                idx -= 1;
            }
        }

        return idx;

    }
};

这里get获得的是（1，nums(i)）的pair数据对，pair的first值都是1,所以大小比较的时候对pair的second值进行大小的比较，这个可以mark一下！

3、解题思路：

（1）当不是峰值时，峰值出现在idx的左边或者右边，索引值idx<idx+1时峰值索引变成idx+1，相反idx<idx-1，峰值索引变为idx-1。

（2）i值大于i+1且i值大于i-1

三、我的暴力解决

  1. class Solution {
  2. public:
  3.     int findPeakElement(vector<int>& nums) {
  4.         int n=nums.size();
  5.         int idx = 0;
  6.         for(int i = 1;i<n-1;i++)
  7.         {
  8.             if(n==2)
  9.             {
  10.                 if(nums[i] > nums[i-1])
  11.                 {
  12.                     idx = i;
  13.                     break;
  14.                 }
  15.                 else if(nums[i] < nums[i-1])
  16.                 {
  17.                    idx = i-1;
  18.                     break; 
  19.                 }
  20.             }
  21.             if(nums[i] > nums[i+1] && nums[i] > nums[i-1]) {
  22.             idx = i;
  23.             break; }
  24.  
  25.         }
  26.  
  27.         return idx;
  28.     }
  29. };

1、测试一：

测试用例失败：nums =[1,2]，输出0，期望是1

调试一下发现循环条件"n<n-1"，当n=2时，n<1,n从1开始，所以没有进入循环判断"if(n==2)"的条件，测试nums =[1,2]案例失败。

修改while循环条件，得到正确输出：

但是，似乎不行呀，执行nums=[1,2,3,4]的时候，没有峰值，所以出错

所以，我发现，官方给的答案确实有他的道理！！！这里没考虑峰值为单边的情况，比如只有上坡或者只有下坡，单独“if (nums[i] > nums[i + 1] && nums[i] > nums[i - 1])”就会报以上的错误了。

2、测试二：

考虑新增上下坡的情况判断 

  1. if (i + 1 == n)
  2.         {
  3.             if (nums[i] > nums[i - 1])
  4.             {
  5.                 idx = i;
  6.                 break;
  7.             }
  8.             if (nums[i] < nums[i - 1])
  9.             {
  10.                 break;
  11.             }
  12.         }

Yes，测试下坡vector<int> nums = {4,3,2,1}通过： 测试上坡vector<int> nums = {1,2,3,4}通过：

3、最终“暴力求解”代码：

在vs上测试代码Solution.cpp、Solution.h、 main.cpp

Solution.cpp

  1. #include "Solution.h"
  2.  
  3. int Solution::findPeakElement(vector<int>& nums)
  4. {
  5.     int n = nums.size();
  6.     int idx = 0;
  7.     for (int i = 1; i < n ; i++)
  8.     {
  9.         if (n == 2)
  10.         {
  11.             if (nums[i] > nums[i - 1])
  12.             {
  13.                 idx = i;
  14.                 break;
  15.             }
  16.             else if (nums[i] < nums[i - 1])
  17.             {
  18.                 idx = i - 1;
  19.                 break;
  20.             }
  21.         }
  22.         if (i + 1 == n)
  23.         {
  24.             if (nums[i] > nums[i - 1])
  25.             {
  26.                 idx = i;
  27.                 break;
  28.             }
  29.             if (nums[i] < nums[i - 1])
  30.             {
  31.                 break;
  32.             }
  33.         }
  34.         if (nums[i] > nums[i + 1] && nums[i] > nums[i - 1]) {
  35.             idx = i;
  36.             break;
  37.         }
  38.  
  39.     }
  40.  
  41.     return idx;
  42. }
  43.  
  44.

Solution.h

  1. #pragma once
  2. #include<vector>
  3. using namespace std;
  4. class Solution
  5. {
  6. public:
  7. 	int findPeakElement(vector<int>& nums);
  8. };
  9.

 mian.cpp

  1. #include<iostream>
  2. using namespace std;
  3. #include"Solution.h"
  4.  
  5. int main()
  6. {
  7.     vector<int> nums = {4,3,2,1};
  8.     
  9.     Solution Func;
  10.     int index = Func.findPeakElement(nums);
  11.  
  12.     cout << index << endl;
  13. }

4、官网提交测试通过：

 5、解题思路：

  • 首先想到nums的峰值元素满足条件1：if(nums[i]>nums[i+1]&&nums[i]<nums[i-1]);
  • 提交1后，nums=[1]只有一个元素时，idx应该返回0;所以idx初始值为0;
  • 提交2后，nums=[1,2]只有两个元素时，idx应该等于较大元素,增加两个元素时条件2:if(n==2)时idx=较大值索引；
  • 提交3后，只有上下坡报错，新增条件3：nums=[1,2,3,4]上坡时，idx应该等于最后一个元素的索引;下坡nums=[4,3,2,1]时，idx应该等于最后一个元素的索引；
  • 注意for循环范围for (int i = 1; i < n ; i++)。

四、c++函数max_element（）解决

我真的栓Q了，原来函数解决这么简单哦！ 

1、函数使用介绍：

max_element（）与min_element（）分别用来求vector容器的最大元素和最小元素的位置。

  1. 1）vector容器
  2. vector<int> n;
  3. int maxPosition = max_element(n.begin(),n.end()) - n.begin(); //最大值下标
  4. int minPosition = min_element(n.begin(),n.end()) - n.begin();//最小值下标
  5.  
  6. 2）普通数组
  7. int a[]={1,2,3,4};
  8. int maxPosition = max_element(a,a+4) - a; //最大值下标
  9. int minPosition = min_element(a,a+4) - a;//最小值下标
  10.  
  11. 3）最大值最小值
  12. int maxValue1 = *max_element(nums.begin(), nums.end()); //vector最大值
  13. int minValue1 = *min_element(nums.begin(), nums.end());//vector最小值
  14. int maxValue2 = *max_element(a, a + 4); //a[]最大值
  15. int minValue2 = *min_element(a, a + 4);//a[]最小值

2、max_element（） 峰值寻找完整代码：

  1. #include<iostream>
  2. using namespace std;
  3. #include <algorithm>
  4.  
  5. int main()
  6. {
  7.     vector<int> nums = {4,3,2,1};
  8.  
  9.     int index = max_element(nums.begin(), nums.end()) - nums.begin(); //最大值下标
  10.     cout <<"vector下最大值下标：" << index << endl;
  11.  
  12.     int a[] = { 4,3,2,1 };
  13.     int maxIdx = max_element(a, a + 4) - a;
  14.     cout << "a[]   下最大值下标："  << maxIdx << endl;
  15.  
  16.     int maxValue1 = *max_element(nums.begin(), nums.end()); //最大值
  17.     int minValue1 = *min_element(nums.begin(), nums.end());//最小值
  18.     int maxValue2 = *max_element(a, a + 4); //最大值
  19.     int minValue2 = *min_element(a, a + 4);//最小值
  20.  
  21.     cout << "vector下的max值：" << maxValue1 << "  min值：" << minValue1 << endl;
  22.     cout << "a[]   下的max值：" << maxValue1 << "  min值：" << minValue2 << endl;
  23.  
  24. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/509894
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号