【每日一题】寻找峰值

发布时间:2023年12月18日

Tag

【二分查找】【数组】【2023-12-18】


题目来源

162. 寻找峰值


解题思路

方法一:二分查找

思路

进行二分查找,记当前的二分中点为 mid

  • 如果 nums[mid] < nums[mid + 1],则说明在 mid+1 位置及其右侧存在高峰,则可以在 [mid + 1, r] 中继续二分查找;
  • 如果 nums[mid] >= nums[mid + 1],则说明在 mid 位置及其左侧存在高峰,则可以在 [l, mid] 中继续二分查找。

算法

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size(); 
        int l = 0, r = n - 1;
        int mid;

        while(l < r){
            mid = (l + r) >> 1;
            if(nums[mid] < nums[mid + 1]){
                l = mid + 1;
            }
            else{
                r = mid;
            }
        }
        return l;
    }
};

复杂度分析

时间复杂度: O ( l o g n ) O(logn) O(logn) n n n 为数组 nums 的长度。

空间复杂度: O ( 1 ) O(1) O(1)


写在最后

如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。

最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。

文章来源:https://blog.csdn.net/weixin_54383080/article/details/135053518
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。