admin管理员组

文章数量:1487745

寻找峰值题目解析

一、题目描述

162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

代码语言：javascript代码运行次数：0运行复制
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

代码语言：javascript代码运行次数：0运行复制
输入：nums = [1,2,1,3,5,6,4]输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

二、题目解析

本题更是一个不是有序数组，但是可以完美使用二分的题目，很经典！

主要注重二段性的查找。

因为数组两端的值都是负无穷，我们可以总结出两条规律，求出mid下标的值，然后跟mid+1位置的值比较，分为两大类，由此可以实现二段性的划分。

三、原码

代码语言：javascript代码运行次数：0运行复制
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0;
        int right = nums.size()-1;
        int mid = 0;
        while(left < right)
        {
            mid = left + (right-left+1)/2;
            if(nums[mid] > nums[mid-1])
                left = mid;
            else
                right = mid-1;
        }
        return left;
    }
};
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-15，如有侵权请联系 cloudcommunity@tencent 删除数组算法索引int函数

本文标签： 寻找峰值题目解析

版权声明：本文标题：寻找峰值题目解析 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/shuma/1754809807a3179862.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。