一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2167|回复: 6
收起左侧

[算法题] lintcode Find Peak Element II 一问

[复制链接] |试试Instant~ |关注本帖
oio14644 发表于 2015-5-27 13:22:16 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 oio14644 于 2015-5-27 13:54 编辑

file:///C:/Users/WEIWAN~1/AppData/Local/Temp/%W@GJ$ACOF(TYDYECOKVDYB.png原题在这里
http://www.lintcode.com/en/problem/find-peak-element-ii/
参考别人的答案,自己鼓捣一个出来,能通过,但是不是很理解
if (A[i+1][j] > A[j+1]) {
i++;
}else {
j++;
}
这一段,
谁能给解释一下?谢谢

class Solution {
    /**
     * @param A: An integer matrix
     * @return: The index of the peak
     */
    public List<Integer> findPeakII(int[][] A) {
    List<Integer> res = new ArrayList<Integer>();
                if (A == null || A.length == 0 || A[0].length == 0) {
                    return res;
                }
                int row = A.length-1;
                int col = A[0].length-1;
                int i = 1;
                int j = 1;
                while (i < row && j < col) {
                                if (A[i-1][j] < A[j] && A[i+1][j] < A[j]
                                 && A[j+1] < A[j] && A[j+1] < A[j]) {
                                        res.add(i);
                                        res.add(j);
                                        return res;
                                }else
                                if (A[i+1][j] > A[j+1]) {//这是为什么?
                                        i++;
                                }else {
                                        j++;
                                }
                        }
                return res;
    }
}
  



kittycerry 发表于 2015-6-23 23:17:16 | 显示全部楼层
这个正是我昨天问的那个
回复 支持 反对

使用道具 举报

senarukana 发表于 2015-6-27 20:22:09 | 显示全部楼层
答案是错的,case不够强而已。
比如下面这个
{
        {1, 2, 2, 1},
        {2, 3, 4, 2},
        {2, 2, 5, 3},
        {1, 8, 6, 2},
        {0, 2, 1, 0}
}
回复 支持 反对

使用道具 举报

kittycerry 发表于 2015-6-27 23:41:24 | 显示全部楼层
senarukana 发表于 2015-6-27 20:22
答案是错的,case不够强而已。
比如下面这个
{

有什么好的答案推荐么?谢谢!!
回复 支持 反对

使用道具 举报

liux0611 发表于 2015-7-2 23:03:02 | 显示全部楼层
senarukana 发表于 2015-6-27 20:22
答案是错的,case不够强而已。
比如下面这个
{

你这个case是错的,题目说明相邻数字不能相同
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-3 09:50:03 | 显示全部楼层
liux0611 发表于 2015-7-2 23:03
你这个case是错的,题目说明相邻数字不能相同

确实,但是这个例子试图说明的论点依然是成立的。只要简单地把周围一圈数字换成任意的不重复的非常小的数字即可。
回复 支持 反对

使用道具 举报

sqzqkd 发表于 2015-8-2 07:08:35 | 显示全部楼层
这题最好的时间复杂度确实是O(n+m),http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf, 这里有比较清楚的解释和复杂度计算。每次缩小1/4就行。程序写出来有点小长,但是可以AC。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 23:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表