leetcode 74. Search a 2D Matrix 右上角搜索

朱雀 2022-06-08 01:25 171阅读 0赞

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.  
The first integer of each row is greater than the last integer of the previous row.  
For example,

Consider the following matrix:

\[  
\[1, 3, 5, 7\],  
\[10, 11, 16, 20\],  
\[23, 30, 34, 50\]  
\]  
Given target = 3, return true.

这道题考察的是在一个排序的矩阵中搜索目标元素，最容易想到的就是先按照第一列做搜索，然后针对目标行做二分搜索。

还有一种很简单的方法就是使用右上角元素搜索。

代码如下：

public class Solution
    {
        /*
         * 这个方法是我写的：右上角元素比较法，是一个本很棒的方法，指的学习
         * */
        public boolean searchMatrix1111(int[][] matrix, int target)
        {
            if(matrix==null || matrix.length<=0 || matrix[0].length<=0 
            || target<matrix[0][0] || target>matrix[matrix.length-1][matrix[0].length-1])
                return false;
    
            int row=0,col=matrix[0].length-1;
            while(row<matrix.length && col>=0)
            {
                if(target==matrix[row][col])
                    return true;
                else if(target>matrix[row][col])
                    row++;
                else 
                    col--;
            }
            return false;
        }
    
    
        /*
         * 这个是二分搜索方法，先按照第一列搜索，然后按照对应的行搜索
         * */
        public boolean searchMatrix(int[][] matrix, int target)
        {
            //特殊情况，这个很蛋疼
            if(matrix==null || matrix.length<=0 || matrix[0].length<=0
            || target<matrix[0][0] || target>matrix[matrix.length-1][matrix[0].length-1])
                return false;
    
            int row=0;
            for(int i=0;i<matrix.length;i++)
            {
                if(target == matrix[i][0])
                    return true;
                else if(target < matrix[i][0])
                {
                    row=i-1;
                    break;
                }
    
                if(i==matrix.length-1)
                    row=i;
            }
    
            int beg=0,end=matrix[0].length-1;
            while(beg<=end)
            {
                //注意要这种表述，以防溢出
                int mid=(end-beg)/2+beg;
                if(matrix[row][mid]==target)
                    return true;
                else if(matrix[row][mid] < target)
                    beg=mid+1;
                else
                    end=mid-1;
            }
            return false;
        }
    }

下面的是C++的做法，使用右上角搜索方法，直接去做

代码如下：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    class Solution 
    {
    public:
        bool searchMatrix(vector<vector<int>>& mat, int target)
        {
            if (mat.size() <= 0 || mat[0].size() <= 0 || mat[mat.size() - 1][mat[0].size() - 1] < target)
                return false;
    
            int i = 0, j = mat[0].size()-1;
            while (i < mat.size() && j >= 0)
            {
                if (target == mat[i][j])
                    return true;
                else if (target > mat[i][j])
                    i++;
                else
                    j--;
            }
            return false;
        }
    };