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

二维数组中的查找

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

相关推荐

不愿透露姓名的神秘牛友
11-27 10:46
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务