题解 | #二维数组中的查找#

二维数组中的查找

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

//方法一:暴力解法,两层遍历矩阵。时间复杂度为:O(n^m)
//方法二:二分法,两层遍历矩阵。时间复杂度为:O(n*logm)
public class Solution {
    public boolean Find(int target, int [][] array) {
//         //方法一:暴力解法,两层遍历矩阵。时间复杂度为:O(n^m)
//         int length = array.length;//一维数组长度
//         //空数组处理
//         if(length == 0){
//             return false;
//         }
//         int len = array[0].length;//二维数组长度
//         //遍历
//         for(int i=0;i<length;i++){
//             for(int j=0;j<len;j++){
//                 if(array[i][j] == target){
//                     return true;
//                 }
//             }
//         }

//         return false;
        
        //方法二:二分法,两层遍历矩阵。时间复杂度为:O(n*logm)
        int length = array.length;//一维数组长度
        //空数组处理
        if(length == 0){
            return false;
        }
        for(int i=0;i<length;i++){//将每一维数组都使用二分法查找
            if(find(target,array,i)){
                return true;
            }
        }
        
        return false;
    }
    
    public boolean find(int target,int[][] array,int i){
        int len = array[i].length;
        //特殊值处理
        if(len == 0){
            return false;
        }
        int min = 0;//最小值索引
        int max = len-1;//最大值索引
        int mid = (min+max)/2;//中值索引
        while(min<=max){//循环结束条件
            if(array[i][mid] == target){//找到目标值
                return true;
            }else if(array[i][mid] > target){//中值大于目标值,目标值在左区间
                max = mid - 1;//更新最大值
            }else{//中值小于目标值,目标值在右区间
                min = mid + 1;//更新最小值
            }
            mid = (min+max)/2;//更新中值
        }
        if(min>max){//判断退出while循环的方式,一是return终止循环,二是条件不满足是退出循环
            return false;
        }
        
        return true;//没有意义的返回值
    }
}
全部评论

相关推荐

06-25 09:33
厦门大学 Java
球球别拷打俺了:现在日常估计没啥hc了,等到八月多估计就慢慢有了。双九✌🏻不用焦虑的
投递快手等公司10个岗位
点赞 评论 收藏
分享
07-17 12:07
门头沟学院 Java
勇敢牛牛不怕困难
投递OPPO等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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