162. Find Peak Element

發表於 | 分類於

problem

solution

option 1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        // brute force
        int n = nums.size();
        if(n==1 || nums[0]>nums[1]) return 0;
        if(nums.back() > nums[n-2]) return n-1;
        for(int i=1;i<n-1;++i){
            if(nums[i]>nums[i-1] && nums[i] > nums[i+1]) return i;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        int l= 0, r = n-1;
        while(l<r){
            int mid = l + (r-l)/2;
            if(nums[mid]< nums[mid+1]) l =mid+1;
            else r = mid;
        }
        return r;
    }
};

analysis

  • option 1
  • time complexity O(n) O(logn)
  • space complexity O(1)