• 240. 搜索二维矩阵 II


    编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

    • 每行的元素从左到右升序排列。
    • 每列的元素从上到下升序排列。

    示例 1:

    输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
    输出:true
    

    示例 2:

    输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
    输出:false
    

    提示:

    • m == matrix.length
    • n == matrix[i].length
    • 1 <= n, m <= 300
    • -109 <= matrix[i][j] <= 109
    • 每行的所有元素从左到右升序排列
    • 每列的所有元素从上到下升序排列
    • -109 <= target <= 109

     

      //按行二分查找,行不变,返回对应列下标

        int findRow(vector>& matrix,int row,int target)

        {

            if(matrix[row][0]>target)

            {

                return -1;

            }

            //int m=matrix.size();

            int n=matrix[0].size();

            int left=0;

            int right=n-1;

            int mid=(left+right)/2;

            while(left<=right)

            {

                mid=(left+right)/2;

                if(target==matrix[row][mid])

                {

                    return mid;

                }

                if(target > matrix[row][mid])

                {

                    left=mid+1;

                }

                else

                {

                    right=mid-1;

                }

            }

            return -1;

        }

         int findCol(vector>& matrix,int col,int target)

        {

            if(matrix[0][col]>target)

            {

                return -1;

            }

            int m=matrix.size();

            //int n=matrix[0].size();

            int left=0;

            int right=m-1;

            int mid=(left+right)/2;

            while(left<=right)

            {

                mid=(left+right)/2;

                if(target==matrix[mid][col])

                {

                    return mid;

                }

                if(target > matrix[mid][col])

                {

                    left=mid+1;

                }

                else

                {

                    right=mid-1;

                }

            }

            return -1;

        }

        bool searchMatrix(vector>& matrix, int target) {

            if(matrix[0][0]>target)

            {

                return false;

            }  

            int m=matrix.size();

            int n=matrix[0].size();

            if(findRow(matrix,0,target)!= -1)

            {

                return true;

            }

            for(int i=0;i

            {

                if(findCol(matrix,i,target)!= -1)

                {

                    return true;

                }

            }

            return false;

        }

  • 相关阅读:
    Java基础:Java抽象接口
    短期动态IP介绍
    @Autowired注解推荐使用方法:用在构造方法上
    性格急躁怎么办?如何改变急躁的性格?
    python基础--函数的应用、lambda表达式以及高阶函数
    python AIOT教程一1.必备多元函数微分学理论基础
    LCR 180.文件组合
    使用Mock技术帮助提升测试效率的小tips,你知道几个?
    MATLAB函数:filtfilt——零相位数字滤波
    普元中间件Primeton AppServer6.5部署SuperMap iServer
  • 原文地址:https://blog.csdn.net/yinhua405/article/details/134544661