📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 7411| 回复: 7
跳转到指定楼层
上一主题 下一主题
收起左侧

lintcode Find Peak Element II 一问

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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;
    }
}
  




上一篇:二分查找的边界以及返回值问题
下一篇:Word Ladder
推荐
sqzqkd 2015-8-2 07:08:35 | 只看该作者
全局:
这题最好的时间复杂度确实是O(n+m),http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf, 这里有比较清楚的解释和复杂度计算。每次缩小1/4就行。程序写出来有点小长,但是可以AC。

评分

参与人数 2大米 +13 收起 理由
BuFann + 3 太棒了!
vancexu + 10 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
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是错的,题目说明相邻数字不能相同

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

使用道具 举报

🔗
BuFann 2018-7-12 04:42:25 | 只看该作者
全局:
sqzqkd 发表于 2015-8-2 07:08
这题最好的时间复杂度确实是O(n+m),http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf, ...

这个题目和slides上的题目还不太一样。
这个题目对于每个column不需要找global max只需要用二分法找local max就可以了。找一个row的local max需要O(logn)的时间,然后一共有O(logm)的row,所以总的时间复杂度是O(logn * logm),比O(m + n)要小。
如果是slides上的那个题,由于没有保证边界一定是小于临近边界的节点的,就不能简单的使用local max因为会被带偏,所以用相似的解法,在每个row上找global max需要O(n)的时间,然后又O(logm)个row,一共就是O(n logm)的时间。所以后续他才提出了O(m + n)的解法,比O(logm*logn)要差,但是在这种题设下是最好的了。
实际的代码运行速度也说明了这个。

补充内容 (2018-7-12 04:56):
不同点其实不在于边界的情况,而是在于有没有重复。slides里的可以有重复,所以无法使用二分找local max,但是lintcode上的可以二分所以可以logn * logm解决。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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