二维数组查找,上下左右四个边界缩小,为啥会超时啊?

二维数组中的查找

http://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e

求个大佬帮我看下为啥会超时,用的是从上下左右四个边界缩,直到只有一个元素的方法。

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length==0||array[0].length==0)return false;
        int rowl=0,rowr=array.length-1;
        int coll=0,colr=array[0].length-1;
        int temp1;
        int temp2;
        while(true){
            temp1=array[rowl][coll];
            temp2=array[rowr][colr];
            if(temp1==target)return true;
            if(temp1>target||temp2<target)return false;
            while(array[rowr][coll]>target&&rowr>rowl)rowr--;
            while(array[rowl][colr]<target&&rowl<rowr)rowl++;

            while(array[rowr][coll]<target&&coll<colr)coll++;
            while(array[rowl][colr]>target&&coll<colr)colr--;
        }
    }
}
全部评论
超时是因为程序进入了死循环,您的代码是使用左下、右上两个元素来改变边界,而使用左上、右下元素来判断是否终止算法,当数组中只有一个目标元素时,程序不会有问题,但是当数组中存在多个目标时,就可能出现目标元素卡在边界左下、右上的情况,这会使边界无法移动,终止条件也不会被触发,从而造成死循环。解决方法是使用四个元素中的其它元素来进行true判断。 这里构造一个会导致死循环的测试用例:{{1,2,3}, {2,3,4}, {3,4,5}}, target=3
2 回复 分享
发布于 2020-09-05 20:35

相关推荐

哈哈哈哈哈哈哈哈哈哈这个世界太美好了
凉风落木楚山秋:毕业出路老师不管,你盖个章他好交差就完事了,等你盖完毕业了就不关他事情了
点赞 评论 收藏
分享
lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。 时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务