Find Peak Element II

Description:

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.

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])

Note

The matrix may contains multiple peeks, find any of them.

Challenge

Solve it in O(n+m) time.

If you come up with an algorithm that you thought it is O(n log m) or O(m log n), can you prove it is actually O(n+m) or propose a similar but O(n+m) algorithm?

Solution:

Reference: http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

class Solution { public: /** * @param A: An integer matrix * @return: The index of the peak */ vector<int> findPeakII(vector<vector<int> > A) { auto m = (int)A.size(); auto n = (int)A[0].size(); int up = 0; int down = m-1; int left = 0; int right = n-1; while (left <= right && up <= down) { int midRow = up+down>>1; int maxCol = findPeakInRow(A, midRow, left, right); if (A[midRow][maxCol] < A[midRow-1][maxCol]) down = midRow-1; else if (A[midRow][maxCol] < A[midRow+1][maxCol]) up = midRow+1; else return vector<int>({midRow, maxCol}); int midCol = left+right>>1; int maxRow = findPeakInCol(A, midCol, up, down); if (A[maxRow][midCol] < A[maxRow][midCol-1]) right = midCol-1; else if (A[maxRow][midCol] < A[maxRow][midCol+1]) left = midCol+1; else return vector<int>({maxRow, midCol}); } return vector<int>({up, left}); } private: int findPeakInRow(vector<vector<int>>& A, int i, int left, int right) { int rc = left; for (int j = left+1; j < right; ++j) if (A[i][j] > A[i][rc]) rc = j; return rc; } int findPeakInCol(vector<vector<int>>& A, int j, int up, int down) { int rc = up; for (int i = up+1; i < down; ++i) if (A[i][j] > A[rc][j]) rc = i; return rc; } };

转载于:https://www.cnblogs.com/deofly/p/find-peak-element-ii.html

相关资源：JAVA上百实例源码以及开源项目