c*n
2 楼
http://www.lintcode.com/en/problem/find-peak-element-ii/
anybody has some hints ?
(too bad lintcode doesn't have discussion forums)
anybody has some hints ?
(too bad lintcode doesn't have discussion forums)
t*1
3 楼
想买红色的 ，求推荐
z*0
4 楼
same here
g*c
5 楼
divide and conquer ? 矩阵中间一个十字的边界divide。 扫边界的中心来确定move到
哪一块。一共只扫m+n个边界元素。
哪一块。一共只扫m+n个边界元素。
m*2
6 楼
same
j*g
7 楼
看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
个2.
O(n)的 复杂度过不了 case 15, 坑爹啊
， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
个2.
O(n)的 复杂度过不了 case 15, 坑爹啊
d*2
8 楼
same
【在 a******n 的大作中提到】
: 哈哈，这种情况，到底可以拿到rebate吗。。。
【在 a******n 的大作中提到】
: 哈哈，这种情况，到底可以拿到rebate吗。。。
c*n
9 楼
hmmm. 猛一看觉得不 work, 写了个例子， 能行。 要看看证明。。。
【在 j********g 的大作中提到】
: 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
: ， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
: 或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
: 个2.
: O(n)的 复杂度过不了 case 15, 坑爹啊
【在 j********g 的大作中提到】
: 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
: ， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
: 或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
: 个2.
: O(n)的 复杂度过不了 case 15, 坑爹啊
g*e
10 楼
same
n*u
11 楼
规则是：
1.相邻的数字肯定不同，所以每走一步不是变大就是变小。
2.最边缘的肯定比里面那层低。
所以可以很无耻的，从A[1][1]开始向右下（或者从任何一个角落对角线的走），如果
右边或者下边有更高的，就往高的走，如果怎么走都更高，到了边缘肯定会低下去的。
就是那儿了。
题目是让找任何一个peak，不是找最高的那个。
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
i = 1
j = 1
while i < len(A) and j < len(A[0]):
if A[i+1][j] > A[i][j] and A[i][j+1] > A[i][j]:
if A[i+1][j] > A[i][j+1]:
i += 1
else:
j += 1
elif A[i+1][j] > A[i][j]:
i += 1
elif A[i][j+1] > A[i][j]:
j += 1
else:
return [i,j]
1.相邻的数字肯定不同，所以每走一步不是变大就是变小。
2.最边缘的肯定比里面那层低。
所以可以很无耻的，从A[1][1]开始向右下（或者从任何一个角落对角线的走），如果
右边或者下边有更高的，就往高的走，如果怎么走都更高，到了边缘肯定会低下去的。
就是那儿了。
题目是让找任何一个peak，不是找最高的那个。
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
i = 1
j = 1
while i < len(A) and j < len(A[0]):
if A[i+1][j] > A[i][j] and A[i][j+1] > A[i][j]:
if A[i+1][j] > A[i][j+1]:
i += 1
else:
j += 1
elif A[i+1][j] > A[i][j]:
i += 1
elif A[i][j+1] > A[i][j]:
j += 1
else:
return [i,j]
D*9
12 楼
same
c*n
13 楼
你这个逻辑不对吧（即使最后结果对）
“如果怎么走都更高，到了边缘肯定会低下去的” ---- 这个只能说你走的1维的（曲
折的） 路线上有一个1维的peak, 人要求是十字的peak
【在 n*********u 的大作中提到】
: 规则是：
: 1.相邻的数字肯定不同，所以每走一步不是变大就是变小。
: 2.最边缘的肯定比里面那层低。
: 所以可以很无耻的，从A[1][1]开始向右下（或者从任何一个角落对角线的走），如果
: 右边或者下边有更高的，就往高的走，如果怎么走都更高，到了边缘肯定会低下去的。
: 就是那儿了。
: 题目是让找任何一个peak，不是找最高的那个。
: class Solution:
: #@param A: An list of list integer
: #@return: The index of position is a list of integer, for example [2,2]
“如果怎么走都更高，到了边缘肯定会低下去的” ---- 这个只能说你走的1维的（曲
折的） 路线上有一个1维的peak, 人要求是十字的peak
【在 n*********u 的大作中提到】
: 规则是：
: 1.相邻的数字肯定不同，所以每走一步不是变大就是变小。
: 2.最边缘的肯定比里面那层低。
: 所以可以很无耻的，从A[1][1]开始向右下（或者从任何一个角落对角线的走），如果
: 右边或者下边有更高的，就往高的走，如果怎么走都更高，到了边缘肯定会低下去的。
: 就是那儿了。
: 题目是让找任何一个peak，不是找最高的那个。
: class Solution:
: #@param A: An list of list integer
: #@return: The index of position is a list of integer, for example [2,2]
e*c
14 楼
same
【在 a******n 的大作中提到】
: 哈哈，这种情况，到底可以拿到rebate吗。。。
【在 a******n 的大作中提到】
: 哈哈，这种情况，到底可以拿到rebate吗。。。
g*c
15 楼
这个复杂度是nlogm吧？
【在 j********g 的大作中提到】
: 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
: ， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
: 或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
: 个2.
: O(n)的 复杂度过不了 case 15, 坑爹啊
【在 j********g 的大作中提到】
: 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
: ， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
: 或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
: 个2.
: O(n)的 复杂度过不了 case 15, 坑爹啊
x*z
16 楼
that is because you are click multiple windows?
j*g
17 楼
O(n) 啊， 每次都砍掉最大值的一半， max(m, n) + max(max(m,n)/2 , min(m,n)) +
...
最后结果上限是4*max(m, n)
比如 M=N =32, 32*32 -> 32*16 -> 16*16 -> 16*8 -> 8*8 -> 8*4 -> 4*4 -> 4*2 ->
2*2 -> 2*1 -> 1*1
相当于 32 + 32 + 16 + 16 + 8 + 8 + 4 + 4 + 2 + 2 -> 2*(n + n/2 + n/4 +... )
-> 4n
【在 g*****c 的大作中提到】
: 这个复杂度是nlogm吧？
...
最后结果上限是4*max(m, n)
比如 M=N =32, 32*32 -> 32*16 -> 16*16 -> 16*8 -> 8*8 -> 8*4 -> 4*4 -> 4*2 ->
2*2 -> 2*1 -> 1*1
相当于 32 + 32 + 16 + 16 + 8 + 8 + 4 + 4 + 2 + 2 -> 2*(n + n/2 + n/4 +... )
-> 4n
【在 g*****c 的大作中提到】
: 这个复杂度是nlogm吧？
d*2
18 楼
怎么办？ 买还是不买？
【在 a******n 的大作中提到】
: 哈哈，这种情况，到底可以拿到rebate吗。。。
【在 a******n 的大作中提到】
: 哈哈，这种情况，到底可以拿到rebate吗。。。
c*n
19 楼
我觉得你的办法好像有问题， 你看下面的图。
我用一个长菱形表示在长轴方向找到那一行/列的一个peak, 假定我图中的过程一直没
有找到2D peak, 那么就是说菱形的中心那点在短轴的方向一直不是peak.
我试图show , 你这个过程可能陷入死循环， 永远找不到一个点它在两个方向都是peak.
下图中如果你从左边那一列开始在列内找peak, 找到最左下角， 然后行内找，找到右
下角， 然后又 这样逆时针找了一圈，又回到起点。
【在 j********g 的大作中提到】
: 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
: ， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
: 或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
: 个2.
: O(n)的 复杂度过不了 case 15, 坑爹啊
我用一个长菱形表示在长轴方向找到那一行/列的一个peak, 假定我图中的过程一直没
有找到2D peak, 那么就是说菱形的中心那点在短轴的方向一直不是peak.
我试图show , 你这个过程可能陷入死循环， 永远找不到一个点它在两个方向都是peak.
下图中如果你从左边那一列开始在列内找peak, 找到最左下角， 然后行内找，找到右
下角， 然后又 这样逆时针找了一圈，又回到起点。
【在 j********g 的大作中提到】
: 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
: ， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
: 或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
: 个2.
: O(n)的 复杂度过不了 case 15, 坑爹啊
a*n
20 楼
没，我就1个window，也没有朋友帮我一起点。。。
【在 x**z 的大作中提到】
: that is because you are click multiple windows?
【在 x**z 的大作中提到】
: that is because you are click multiple windows?
r*7
21 楼
很经典的题目吧，leetcode的find peak element的2维版，解法一样的,nlgn的复杂度
【在 c******n 的大作中提到】
: http://www.lintcode.com/en/problem/find-peak-element-ii/
: anybody has some hints ?
: (too bad lintcode doesn't have discussion forums)
【在 c******n 的大作中提到】
: http://www.lintcode.com/en/problem/find-peak-element-ii/
: anybody has some hints ?
: (too bad lintcode doesn't have discussion forums)
l*8
22 楼
Same
c*n
23 楼
人要求O(M + N), 另外即使NlogN 的话怎么做？ 见上面我画的图
【在 r****7 的大作中提到】
: 很经典的题目吧，leetcode的find peak element的2维版，解法一样的,nlgn的复杂度
【在 r****7 的大作中提到】
: 很经典的题目吧，leetcode的find peak element的2维版，解法一样的,nlgn的复杂度
x*z
24 楼
as long as you have the links in reservation, no problem at all.
【在 a******n 的大作中提到】
: 没，我就1个window，也没有朋友帮我一起点。。。
【在 a******n 的大作中提到】
: 没，我就1个window，也没有朋友帮我一起点。。。
r*7
25 楼
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
最优解是O(N)
【在 c******n 的大作中提到】
: 人要求O(M + N), 另外即使NlogN 的话怎么做？ 见上面我画的图
最优解是O(N)
【在 c******n 的大作中提到】
: 人要求O(M + N), 另外即使NlogN 的话怎么做？ 见上面我画的图
s*x
26 楼
same
j*g
27 楼
我又仔细想了想， 不能每次都砍最大的，那样的话不一定保证最后的是peak.
nlogn比较靠谱。 O(n)的话就只能画十字了。 可以参考算法课件
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
【在 c******n 的大作中提到】
: 人要求O(M + N), 另外即使NlogN 的话怎么做？ 见上面我画的图
nlogn比较靠谱。 O(n)的话就只能画十字了。 可以参考算法课件
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
【在 c******n 的大作中提到】
: 人要求O(M + N), 另外即使NlogN 的话怎么做？ 见上面我画的图
b*r
28 楼
展开讨论讨论什么原因？
c*n
29 楼
多谢，我google 了可能关键词用得不对， 怎么也没有相关的
【在 r****7 的大作中提到】
: http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
: 最优解是O(N)
【在 r****7 的大作中提到】
: http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
: 最优解是O(N)
S*w
30 楼
好牛
【在 j********g 的大作中提到】
: 我又仔细想了想， 不能每次都砍最大的，那样的话不一定保证最后的是peak.
: nlogn比较靠谱。 O(n)的话就只能画十字了。 可以参考算法课件
: http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
【在 j********g 的大作中提到】
: 我又仔细想了想， 不能每次都砍最大的，那样的话不一定保证最后的是peak.
: nlogn比较靠谱。 O(n)的话就只能画十字了。 可以参考算法课件
: http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
S*w
31 楼
lintcode 题目越来越难了
【在 c******n 的大作中提到】
: http://www.lintcode.com/en/problem/find-peak-element-ii/
: anybody has some hints ?
: (too bad lintcode doesn't have discussion forums)
【在 c******n 的大作中提到】
: http://www.lintcode.com/en/problem/find-peak-element-ii/
: anybody has some hints ?
: (too bad lintcode doesn't have discussion forums)
b*5
32 楼
是啊， 所以说， 这CS， 越来越不好找工作。。。
不过， 我去FB， 还有一种叫production engineer， 我到现在没弄懂， production
engineer和ops/service engineer有什么区别。那人还是philosophy， 加political
science专业毕业的。。。 说还有其他人， 也是pholosophy专业毕业的。。。
【在 S***w 的大作中提到】
: lintcode 题目越来越难了
不过， 我去FB， 还有一种叫production engineer， 我到现在没弄懂， production
engineer和ops/service engineer有什么区别。那人还是philosophy， 加political
science专业毕业的。。。 说还有其他人， 也是pholosophy专业毕业的。。。
【在 S***w 的大作中提到】
: lintcode 题目越来越难了
c*n
33 楼
ft. 我照那个pdf 写出来， 也是 15超时
【在 j********g 的大作中提到】
: 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
: ， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
: 或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
: 个2.
: O(n)的 复杂度过不了 case 15, 坑爹啊
【在 j********g 的大作中提到】
: 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
: ， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
: 或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
: 个2.
: O(n)的 复杂度过不了 case 15, 坑爹啊
s*x
34 楼
我也是。。。
【在 c******n 的大作中提到】
: ft. 我照那个pdf 写出来， 也是 15超时
【在 c******n 的大作中提到】
: ft. 我照那个pdf 写出来， 也是 15超时
n*u
35 楼
peak.
恩，我也发现了那里的bug case。
但是好像稍微再慢一点就过不了最后两个test了。。。
lintcode有没有讨论版？提个意见啥的？
【在 c******n 的大作中提到】
: 我觉得你的办法好像有问题， 你看下面的图。
: 我用一个长菱形表示在长轴方向找到那一行/列的一个peak, 假定我图中的过程一直没
: 有找到2D peak, 那么就是说菱形的中心那点在短轴的方向一直不是peak.
: 我试图show , 你这个过程可能陷入死循环， 永远找不到一个点它在两个方向都是peak.
: 下图中如果你从左边那一列开始在列内找peak, 找到最左下角， 然后行内找，找到右
: 下角， 然后又 这样逆时针找了一圈，又回到起点。
x*9
36 楼
case 15 judge有问题。。。已经联系修复好了。。。
直接随机取起始点，然后贪心找局部最大值。。。最差O(n^2)，也可以过。。。
当然，你也可以算一下纯随机，取到局部最大值的概率，(4!/5!) = 1/5，理论上时间
复杂度是O(1)，但是会被极端数据卡，哈哈。
直接随机取起始点，然后贪心找局部最大值。。。最差O(n^2)，也可以过。。。
当然，你也可以算一下纯随机，取到局部最大值的概率，(4!/5!) = 1/5，理论上时间
复杂度是O(1)，但是会被极端数据卡，哈哈。
r*g
37 楼
这里给出了两种解法。
http://www.tangjikai.com/algorithms/lintcode-390-find-peak-elem
对 divide&conque，虽然听起来很straightforward，但是严格的数学证明其实不简单。
我想了一下，还是用数学反证发。
命题：
先沿着中间一row找到那一row的 peak，如果纵向也是peak，则返回；否则，沿着和
peak同一column，neighbor升高的方向recursively搜索 。反复这样操作，必然会找到
peak。
反证：
假设按照这种搜索方法一直找不到peak。那么每次identify搜索方向的peak时，必然该
点高度比前一个搜索方向peak值高。而假设时始终找不到真正的peak（二维上的），所
以，recursion会无限循环下去，高度值会被不断无限制的提高。这显然是和题目条件
conflict的，即每个点高度都是有限的。
不知道这样说的通否。
【在 c******n 的大作中提到】
: http://www.lintcode.com/en/problem/find-peak-element-ii/
: anybody has some hints ?
: (too bad lintcode doesn't have discussion forums)
http://www.tangjikai.com/algorithms/lintcode-390-find-peak-elem
对 divide&conque，虽然听起来很straightforward，但是严格的数学证明其实不简单。
我想了一下，还是用数学反证发。
命题：
先沿着中间一row找到那一row的 peak，如果纵向也是peak，则返回；否则，沿着和
peak同一column，neighbor升高的方向recursively搜索 。反复这样操作，必然会找到
peak。
反证：
假设按照这种搜索方法一直找不到peak。那么每次identify搜索方向的peak时，必然该
点高度比前一个搜索方向peak值高。而假设时始终找不到真正的peak（二维上的），所
以，recursion会无限循环下去，高度值会被不断无限制的提高。这显然是和题目条件
conflict的，即每个点高度都是有限的。
不知道这样说的通否。
【在 c******n 的大作中提到】
: http://www.lintcode.com/en/problem/find-peak-element-ii/
: anybody has some hints ?
: (too bad lintcode doesn't have discussion forums)
q*t
38 楼
我记得算法棵第一节课就是讲这个的
相关阅读
谁想要二手的clarisonic 洗脸刷 mia 就用过一次，不喜欢闲置了这个算好deal吗 guess 过膝皮靴 51刀（含税免运费）转让coach factory 30% off coupon求推荐，治疗面部湿疹,有人用过cbh的湿疹套装吗？Lady Gaga 走古典爵士路线了女明星的模特范儿求推荐精华回国送礼的首饰【求】A&F25%off couponStella mid-heel bootie ( what do you think #1, #2)A&F 25% off code推荐个片吧-命运交响曲还不错～发现一个纯天然大眼美女不知不觉屯了很多La Mer的小样（加了一些产品点评）AE, Aerie & 77kids奔一组胶片和数码拍摄的portraitsDEAL: Lancome 7-Piece Gift (Bloomingdales)那个霍建华也长得太美了coach 100 off 300 give away请JMS帮忙选一个LV的包包