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

二维数组中的查找

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

相关推荐

三年之期已到我的offer快到碗里来:9硕都比不上9本
点赞 评论 收藏
分享
Yushuu:你的确很厉害,但是有一个小问题:谁问你了?我的意思是,谁在意?我告诉你,根本没人问你,在我们之中0人问了你,我把所有问你的人都请来 party 了,到场人数是0个人,誰问你了?WHO ASKED?谁问汝矣?誰があなたに聞きましたか?누가 물어봤어?我爬上了珠穆朗玛峰也没找到谁问你了,我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒,在找到谁问你之前我连癌症的解药都发明了出来,我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了😆
点赞 评论 收藏
分享
美团 后端开发 总包n(15%是股票)
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务