当前位置：网站首页>Sword finger offer (2nd Edition) brush questions | 04 Find in 2D array

Sword finger offer (2nd Edition) brush questions | 04 Find in 2D array

2022-06-21 07:20:00 【wx5ab712ac69546】

Catalog

The finger of the sword Offer 04. Search in a two-dimensional array

In a n * m In a two-dimensional array , Each row is sorted in ascending order from left to right , Each column is sorted in ascending order from top to bottom . Please complete an efficient function , Enter such a two-dimensional array and an integer , Determine whether the array contains the integer .

Example :

The existing matrix matrix as follows ：

       
        [
        
  [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]
        
]
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.

Given target = 5, return true.

Given target = 20, return false.

Limit ：

0 <= n <= 1000

0 <= m <= 1000

My solution ： Dichotomy

The finger of the sword Offer（ The first 2 edition ） Brush problem | 04. Search in a two-dimensional array _ Two points search

       
        class Solution {
        
    int m,n;
        
public:
        
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        
        // Input legitimacy judgment 
        
        if(matrix.size() == 0 )//if(matrix[0].size()==0) wrong ,matrix It's empty ,matrix[0] error 
        
        {
        
            return false;
        
        }
        
        m = matrix.size(); n = matrix[0].size();
        
        // Line by line binary traversal search 
        
        for(int j = 0; j < m; j++)
        
        {
        
            // Binary search of the current row 
        
            int low = 0;
        
            int high = n - 1;
        
            int mid = (low + high) / 2;
        
            while (low <= high)
        
            {
        
                if (matrix[j][mid] == target)
        
                {
        
                    return true;
        
                }
        
                else if (target < matrix[j][mid])
        
                {
        
                    high = mid-1;
        
                }
        
                else
        
                {
        
                    low = mid + 1;
        
                }
        
                mid= (low + high) / 2;
        
            }
        

        
        }
        
        return false;// All rows not found , Return none 
        
    }
        
};
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.
        25.
        26.
        27.
        28.
        29.
        30.
        31.
        32.
        33.
        34.
        35.
        36.
        37.
        38.

       
        class Solution {
        
    int m , n;
        
public:
        
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        
        // Input legitimacy judgment 
        
        m = matrix.size();
        
        if( m == 0 )
        
        {
        
            return false;
        
        }
        
        n = matrix[0].size();// Must be on m==0 After judging the conditions , Put it in matrix Null error 
        
        // Line by line binary traversal search 
        
        for(int j = 0; j < m; ++j)
        
        {
        
            // Binary search of the current row 
        
            if(binaryFind(matrix, j, target))
        
                return true;
        
        }
        
        return false;// All rows not found , Return none 
        
    }
        

        
    bool binaryFind(vector<vector<int>>& matrix, int j, int target)
        
    {
        
        int low = 0;
        
        int high = n;
        
        while (low < high)
        
        {
        
            int mid = (low + high) / 2;
        
            if (matrix[j][mid] == target)
        
            {
        
                return true;
        
            }
        
            else if (target < matrix[j][mid])
        
            {
        
                high = mid;
        
            }
        
            else if(target > matrix[j][mid])// This one is direct else No addition if Conditions , It may be slow 4ms
        
            {
        
                low = mid + 1;
        
            }
        
        }
        
        return false;
        
    }
        
};
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.
        25.
        26.
        27.
        28.
        29.
        30.
        31.
        32.
        33.
        34.
        35.
        36.
        37.
        38.
        39.
        40.
        41.
        42.
        43.
        44.

Pit climbing records ：

The finger of the sword Offer（ The first 2 edition ） Brush problem | 04. Search in a two-dimensional array _ Algorithm _02

Line 1033: Char 9: runtime error: reference binding to null pointer of type 'std::vector<int, std::allocator<int>>' (stl_vector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:9

The question is matrix Index out of bounds error caused by null .

namely ：if(matrix[0].size()==0) wrong ,matrix It's empty ,matrix[0] error