leetcode-74-搜索二维矩阵

题目描述：

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:

matrix = [

  [1,   3,  5,  7],

  [10, 11, 16, 20],

  [23, 30, 34, 50]

]

target = 3

输出: true

示例 2:

输入:

matrix = [

  [1,   3,  5,  7],

  [10, 11, 16, 20],

  [23, 30, 34, 50]

]

target = 13

输出: false

要完成的函数：

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

说明：

1、这道题给定一个m行n列的矩阵，要求编写一个高效的算法来判断矩阵中是否含有target这个元素。

如果存在，返回true，否则返回false。

2、这道题其实就是二分法在矩阵上的应用，整个矩阵是升序的。

我们先用二分法确定target可能会在哪一行，接着再用二分法确定target在哪一列，或者不存在。

代码如下：（附详解）

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

    {

        if(matrix.size()==0||matrix[0].size()==0)return false;//[]或者[[]]的边界条件

        int hang=matrix.size(),lie=matrix[0].size(),left=0,right=hang-1,med,t;

        while(left<=right)//二分法判断target在哪一行

        {

            med=(left+right)/2;

            if(target<matrix[med][0])

                right=med-1;

            else if(target>matrix[med][lie-1])

                left=med+1;

            else//找到元素在med这一行了

            {

                t=med;

                left=0;

                right=lie-1;

                while(left<=right)//用二分法找到target在哪一列

                {

                    med=(left+right)/2;

                    if(matrix[t][med]==target)//找到了返回true

                        return true;

                    else if(target<matrix[t][med])

                        right=med-1;

                    else

                        left=med+1;

                }

                return false;//target大于当前行最后一个元素或者小于第一个元素，返回false

            }

        }

        return false;//target小于矩阵的第一行第一个元素，或者大于矩阵最后一行最后一个元素，返回false

    }

上述代码实测8ms，beats 97.83% of cpp submissions。

巴特西

leetcode-74-搜索二维矩阵

题目描述：

要完成的函数：

说明：

最新文章

热门文章