c******n
发帖数: 4965 | 1 http://www.lintcode.com/en/problem/find-peak-element-ii/
anybody has some hints ?
(too bad lintcode doesn't have discussion forums) |
g*****c
发帖数: 106 | 2 divide and conquer ? 矩阵中间一个十字的边界divide。 扫边界的中心来确定move到
哪一块。一共只扫m+n个边界元素。 |
j********g
发帖数: 80 | 3 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
个2.
O(n)的 复杂度过不了 case 15, 坑爹啊 |
c******n
发帖数: 4965 | 4 hmmm. 猛一看觉得不 work, 写了个例子， 能行。 要看看证明。。。
【在 j********g 的大作中提到】
: 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
: ， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
: 或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
: 个2.
: O(n)的 复杂度过不了 case 15, 坑爹啊
|
n*********u
发帖数: 1030 | 5 规则是：
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] |
c******n
发帖数: 4965 | 6 你这个逻辑不对吧（即使最后结果对）
“如果怎么走都更高，到了边缘肯定会低下去的” ---- 这个只能说你走的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]
|
g*****c
发帖数: 106 | 7 这个复杂度是nlogm吧？
【在 j********g 的大作中提到】
: 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
: ， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
: 或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
: 个2.
: O(n)的 复杂度过不了 case 15, 坑爹啊
|
j********g
发帖数: 80 | 8 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吧？
|
c******n
发帖数: 4965 | 9 我觉得你的办法好像有问题， 你看下面的图。
我用一个长菱形表示在长轴方向找到那一行/列的一个peak, 假定我图中的过程一直没
有找到2D peak, 那么就是说菱形的中心那点在短轴的方向一直不是peak.
我试图show , 你这个过程可能陷入死循环， 永远找不到一个点它在两个方向都是peak.
下图中如果你从左边那一列开始在列内找peak, 找到最左下角， 然后行内找，找到右
下角， 然后又 这样逆时针找了一圈，又回到起点。
【在 j********g 的大作中提到】
: 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
: ， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
: 或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
: 个2.
: O(n)的 复杂度过不了 case 15, 坑爹啊
|
r****7
发帖数: 2282 | 10 很经典的题目吧，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
发帖数: 4965 | 11 人要求O(M + N), 另外即使NlogN 的话怎么做？ 见上面我画的图
【在 r****7 的大作中提到】
: 很经典的题目吧，leetcode的find peak element的2维版，解法一样的,nlgn的复杂度
|
r****7
发帖数: 2282 | 12 http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
最优解是O(N)
【在 c******n 的大作中提到】
: 人要求O(M + N), 另外即使NlogN 的话怎么做？ 见上面我画的图
|
j********g
发帖数: 80 | 13 我又仔细想了想， 不能每次都砍最大的，那样的话不一定保证最后的是peak.
nlogn比较靠谱。 O(n)的话就只能画十字了。 可以参考算法课件
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
【在 c******n 的大作中提到】
: 人要求O(M + N), 另外即使NlogN 的话怎么做？ 见上面我画的图
|
c******n
发帖数: 4965 | 14 多谢，我google 了可能关键词用得不对， 怎么也没有相关的
【在 r****7 的大作中提到】
: http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
: 最优解是O(N)
|
S***w
发帖数: 1014 | 15 好牛
【在 j********g 的大作中提到】
: 我又仔细想了想， 不能每次都砍最大的，那样的话不一定保证最后的是peak.
: nlogn比较靠谱。 O(n)的话就只能画十字了。 可以参考算法课件
: http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
|
S***w
发帖数: 1014 | 16 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)
|
b**********5
发帖数: 7881 | 17 是啊， 所以说， 这CS， 越来越不好找工作。。。
不过， 我去FB， 还有一种叫production engineer， 我到现在没弄懂， production
engineer和ops/service engineer有什么区别。那人还是philosophy， 加political
science专业毕业的。。。 说还有其他人， 也是pholosophy专业毕业的。。。
【在 S***w 的大作中提到】
: lintcode 题目越来越难了
|
c******n
发帖数: 4965 | 18 ft. 我照那个pdf 写出来， 也是 15超时
【在 j********g 的大作中提到】
: 看m 和 n 哪个大， 然后选择大的那个的中间那行（列）， 找出改行（列）的最大值
: ， 检查这个值上下（左右）两元素， 如果都小于它，那么就找见了。 否则就去上边
: 或下边(左边或右边)， 重复该过程。 复杂度应该是 n + n/2 + n/4 + .... 最多乘
: 个2.
: O(n)的 复杂度过不了 case 15, 坑爹啊
|
s******x
发帖数: 417 | 19 我也是。。。
【在 c******n 的大作中提到】
: ft. 我照那个pdf 写出来， 也是 15超时
|
n*********u
发帖数: 1030 | 20
peak.
恩，我也发现了那里的bug case。
但是好像稍微再慢一点就过不了最后两个test了。。。
lintcode有没有讨论版？提个意见啥的？
【在 c******n 的大作中提到】
: 我觉得你的办法好像有问题， 你看下面的图。
: 我用一个长菱形表示在长轴方向找到那一行/列的一个peak, 假定我图中的过程一直没
: 有找到2D peak, 那么就是说菱形的中心那点在短轴的方向一直不是peak.
: 我试图show , 你这个过程可能陷入死循环， 永远找不到一个点它在两个方向都是peak.
: 下图中如果你从左边那一列开始在列内找peak, 找到最左下角， 然后行内找，找到右
: 下角， 然后又 这样逆时针找了一圈，又回到起点。
|
|
|
x*******9
发帖数: 138 | 21 case 15 judge有问题。。。已经联系修复好了。。。
直接随机取起始点，然后贪心找局部最大值。。。最差O(n^2)，也可以过。。。
当然，你也可以算一下纯随机，取到局部最大值的概率，(4!/5!) = 1/5，理论上时间
复杂度是O(1)，但是会被极端数据卡，哈哈。 |
r********g
发帖数: 219 | 22 这里给出了两种解法。
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
发帖数: 152 | |
