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]
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])
思路是先上下二分，后左右二分．复杂度为T(n) = O(n)+O(n/2)+T(n/2) ...T(n) = O(n)+O(n/2)+O(n/2)+O(n/4) ... = 3*(O(n/2)+O(n/4)+...)=O(n)
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): if not A: return [-1,-1] l = 1 r = len(A[0]) - 2 up = 1 down = len(A) - 2 import sys while l + 1 < r and up + 1 < down: midRow = (up + down)/2 rowMax = - sys.maxint - 1 #max value in the middle row for i in xrange(l, r + 1): #find the max value in the middle row if A[midRow][i] > rowMax: index1 = i rowMax = A[midRow][i] if A[midRow - 1][index1] < rowMax and A[midRow + 1][index1] < rowMax: return [midRow, index1] else: if A[midRow - 1][index1] > rowMax: down = midRow else: up = midRow colMax = -sys.maxint - 1 for j in xrange(up, down + 1): if A[j][index1] > colMax: index2 = j colMax = A[j][index1] if A[index2][index1 - 1] < colMax and A[index2][index1 + 1] < colMax: return [index2, index1] else: if A[index2][index1 -1 ] > colMax: r = index1 else: l = index1 if A[up][l] > A[down][l] or A[up][r] > A[down][r]: first = up else: first = down if A[first][l] > A[first][r]: second = l else: second = r return [first, second]