t****m
发帖数: 140 | 1 http://www.lintcode.com/en/problem/find-peak-element-ii/
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? | b******i
发帖数: 914 | 2 有帖子讨论过
http://www.mitbbs.com/article_t/JobHunting/32967557.html
里面那个pdf我觉得蛮好，不过自己没试过不知道会不会超时
][
【在 t****m 的大作中提到】
: http://www.lintcode.com/en/problem/find-peak-element-ii/
: 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
| w*********e
发帖数: 49 | 3 基本思路还是二分法。
假设有m行，找到m/2行的最大值，这个值大于左右两边（行最大），检查它的上下邻，
如果都比它小，peak found。如果有一个比它大，可以证明必有peak在这半边（这是证
明得关键，因为这个更大值得存在说明这半边矩阵不是complete valley）。可以证明
这个时间复杂度是O(m+n)。
][
【在 t****m 的大作中提到】
: http://www.lintcode.com/en/problem/find-peak-element-ii/
: 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
| t****m
发帖数: 140 | 4 谢谢楼上两位大牛指点
【在 b******i 的大作中提到】
: 有帖子讨论过
: http://www.mitbbs.com/article_t/JobHunting/32967557.html
: 里面那个pdf我觉得蛮好，不过自己没试过不知道会不会超时
:
: ][
|
|
