Leetcode 162: Find Peak Element -- find peak (C + +, Python)

Title address: Find Peak Element

Introduction:

Peak element refers to the element whose value is greater than the left and right adjacent values. Given an input array ≠ nums, where ≠ nums[i+1], find the peak element and return its index. The array may contain multiple peaks, in this case, just return the location of any peak. It can be assumed that ﹣ nums[-1] = nums[n] = - ∞.

Example 1:   
Input: nums = [1,2,3,1] 
Output: 2 
Explanation: 3 is the peak element, and your function should return its index 2.

Example 2: 
Input: nums = [1,2,1,3,5,6,4] 
Output: 1 or 5  
Explanation: your function can return index 1 with a peak element of 2, or index 5 with a peak element of 6.

 

Note: the solution should be O(logN) time complexity.

Topic analysis:

The time complexity of the algorithm is required. Only check whether the numbers in the middle position meet the requirements every time. Update the interval dynamically. Here, use the queue to save the interval range.

C++ version:

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if (nums.size() == 1 || nums[1] < nums[0])
            return 0;
        if (nums[nums.size() - 1] > nums[nums.size() - 2])
            return nums.size() - 1;
        queue<int> idx;
        idx.push(0);
        idx.push(nums.size() - 1);
        while(!nums.empty())
        {
            int first = idx.front();
            idx.pop();
            int end = idx.front();
            idx.pop();
            int mid = (first + end) / 2;
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1])
                return mid;
            if (mid - first > 1)
            {
                idx.push(first);
                idx.push(mid);
            }
            if (end - mid > 1)
            {
                idx.push(mid);
                idx.push(end);
            }
        }
        return nums.size() - 1;            
    }
};

Python version:

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        if len(nums) == 1 or nums[1] < nums[0]:
            return 0
        if nums[-1] > nums[-2]:
            return len(nums) - 1
        idx = []
        idx.append(len(nums) - 1)
        idx.append(0)
        while(len(idx) != 0):
            first = idx.pop()
            end = idx.pop()
            mid = (first + end) // 2
            if nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1]:
                return mid
            if (mid - first > 1):
                idx.append(mid)
                idx.append(first)
            if (end - mid > 1):
                idx.append(end)
                idx.append(mid)
        return len(nums) - 1

 

 

 

 

Tags: Python

Posted on Sun, 03 Nov 2019 14:26:42 -0800 by medusa1414