1-d peak and 2-d peak

Posted on |

1-d peak

leetcode 162. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:**

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

O(n)时间复杂度的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 1:
            return 0
        if nums[0] > nums[1]:
            return 0

        i = 1
        while i <= len(nums) -1 and nums[i] > nums[i-1] :
            i = i + 1
             
        return i - 1

O(logn)的循环实现 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        start = 0
        end = len(nums) - 1
        while start < end:
            mid = (start+end)/2
            if nums[mid] < nums[mid + 1]:
                start = mid + 1
            else:
                end = mid
        return start

分析：

对于任意一个array都会存在peak

思想就是找到一个数组中间的值，如果这个值比左边的小，那么就可以保证左边一定有peak

如果这个值比右边的小，那么就可以保证右边一定有peak

如果这个值比两边大就说明，他自己就是peak

拓展2-d的peak

对于n行m列的数组 找到一个peak

方法就是

  1. 先找到中间的一列m/2

  2. 然后找到这一列的最大值

  3. 然后判断这个值如果小于左边的列，就对左边的数组进行从第一步开始的操作，如果小于右边的列，就对右边的数组进行相应的操作，如果都大于就可以直接返回了

    T(n,m) = T(n,m/2) + O(n) –>找到global maximum

    T(n,1) = O(n)

    T(n,m) = logm * O(n)

O(nlogm)的实现方法