LeetCode 162 Find Peak Element

标签: 二分搜索 LeetCode 发布于:2022-03-04 22:59:12 编辑于:2022-03-04 22:59:17 浏览量:362

概述

https://leetcode.com/problems/find-peak-element/

题目要求 O(logn)

二分搜索

O(logn) 遍历肯定不行啦,排序也不行,二分吗?额,二分也得某种有序呀。

我很好奇最后的形式,是怎么 log n 的。

题目一个约束 nums[i] != nums[i + 1],以及 nums[-1] = nums[n] = -∞ ,这个就很明显了哦。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (true) {
            int m = (l + r) / 2;
            if ((m == 0 || nums[m] > nums[m-1]) && (m + 1 == nums.size() || nums[m] > nums[m+1])) {
                return m;
            } else if (m == 0 || nums[m] > nums[m-1]) {
                if (l == m) return r;
                l = m;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/