Find Peak Element II

Question

There is an integer matrix which has the following features:

The numbers in adjacent positions are different. The matrix has n rows and m columns.

For all i < m, A[0][i] < A[1][i] && A[n - 2][i] > A[n - 1][i].
For all j < n, A[j][0] < A[j][1] && A[j][m - 2] > A[j][m - 1].

We define a position P is a peek if:

A[j][i] > A[j+1][i] && A[j][i] > A[j-1][i] && A[j][i] > A[j][i+1] && A[j][i] > A[j][i-1]

Find a peak element in this matrix. Return the index of the peak.

Have you met this question in a real interview? Yes Example Given a matrix:

[
  [1 ,2 ,3 ,6 ,5],
  [16,41,23,22,6],
  [15,17,24,21,7],
  [14,18,19,20,10],
  [13,14,11,10,9]
]

return index of 41 (which is [1,1]) or index of 24 (which is [2,2])

Thoughts

1. 从中间行，找到这一行的最大数
2. 如果上面数比它大，则上半部必然有一个Peak，对下面也是

二分法

Solution

class Solution:
    #@param A: An list of list integer 
    #@return: The index of position is a list of integer, for example [2,2]
    def findPeakII(self, A):
        # write your code here
        length = len(A)
        if length == 0:
            return 
        if length == 1:
            col = 0
            for idx, num in enumerate(A):
                if num > A[col]:
                    col = idx
            return [0, idx]

        low = 1
        high = length - 2
        while low <= high:
            mid = ( low + high ) / 2
            peakCol = self.findCol(A, mid)
            if (A[mid][peakCol] < A[mid-1][peakCol]):
                high = mid - 1
            elif (A[mid][peakCol] < A[mid+1][peakCol]):
                low = mid + 1
            else:
                return (mid, peakCol)




    def findCol(self, A, mid):
        col = 0
        for i in range(len(A[mid])):
            if A[mid][i] > A[mid][col]:
                col = i

        return col