Leetcode - Search 2D matrix

In daily question brushing

Catalog

GitHub link

LeetCode link 🤨

subject

Example 1：

Example 2：

Topic analysis

Function parameter analysis ：

Code implementation

          Sequential search method

          Dichotomy search

           Two dimensional arrays are opened in the heap

Summary

---

GitHub link

diwei00 (github.com)https://github.com/diwei00  All the codes are in Exercise Submit in Library

LeetCode link 🤨

74. Search for a two-dimensional matrix - Power button （LeetCode）https://leetcode.cn/problems/search-a-2d-matrix/submissions/

subject

Write an efficient algorithm to judge  m x n  Matrix , Is there a target value . The matrix has the following characteristics ：

• The integers in each row are arranged in ascending order from left to right .
• The first integer in each row is greater than the last integer in the previous row .

Example 1：

 Input ：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

 Output ：true

Example 2：

 Input ：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

 Output ：false

Topic analysis

      Because the integers in each row are arranged in ascending order from left to right, and the first integer in each row is greater than the last integer in the previous row , In fact, it means that the data of the whole matrix is arranged in ascending order , It's just a matrix . According to this characteristic, we first need to traverse the data of the last column in the matrix , If this column of data is larger than the target value target Big , That is, the data to be searched must be in this line , Then you only need to traverse this row of data .

      In fact, it is found that the data in the last column is also in ascending order , And each row is also arranged in ascending order , That means we can use the binary search method when traversing the last column and a row of data , But the last number to look up appears on a certain line , Therefore, the binary search method is used when traversing rows .

Function parameter analysis ：

      Generally, the two-dimensional array parameter transmission developed is to directly transmit the address of the first row of the address array , Use array pointers to receive . You can see that the receiving two-dimensional array here is a secondary pointer , In fact, this two-dimensional array is used in the heap malloc Opened up . First open up an array of storage addresses , Then open up many arrays , Save the first address of these arrays , That is, it forms a two-dimensional array . On release , Also release parr Array of this piece , And then release pparr.（ There is code implementation behind ）matrixSize Is the number of rows of the matrix ,matrixColSize Is the address of the number of matrix columns ,target Is the number of targets to find .

Code implementation （ Sequential search method ）

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target)
{
    int row = matrixSize;
    int col = *matrixColSize;
    int i = 0;
    for (i = 0; i < row; i++)
    {
        if (matrix[i][col - 1] > target || matrix[i][col - 1] == target)
        {
            break;
        }
    }
    //for Cycle out , Fixed subscript 
    if (i == row)
    {
        i -= 1;
    }
    int j = 0;
    for (j = 0; j < col; j++)
    {
        if (matrix[i][j] == target)
        {
            return true;
        }
    }
    return false;
}

  Code implementation （ Dichotomy search ）

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target)
{
    int row = matrixSize;
    int col = *matrixColSize;
    int i = 0;
    // Find the line that needs to find the target value 
    for (i = 0; i < row; i++)
    {
        if (matrix[i][col - 1] > target || matrix[i][col - 1] == target)
        {
            break;
        }
    }
    //for Cycle out , Fixed subscript 
    if (i == row)
    {
        i -= 1;
    }
    int left = 0;
    int right = col - 1;
    while (left <= right)
    {
        int mid = (left + right) >> 1;
        if (matrix[i][mid] > target)
        {
            right = mid - 1;
        }
        else if (matrix[i][mid] == target)
        {
            return true;
        }
        else
        {
            left = mid + 1;
        }
    }
    //while If the loop jumps out, the target value cannot be found 
    return false;
}

Code implementation （ Two dimensional arrays are opened in the heap ）

int main()
{
    // Save an array of addresses 
    int** pa = (int**)malloc(sizeof(int) * 3);
    int i = 0;
    int col = 3;
    // Save the array address pa in 
    for (i = 0; i < 3; i++)
    {
        pa[i] = (int*)malloc(sizeof(int) * col);
    }


    for (i = 0; i < 3; i++)
    {
        free(pa[i]);
    }
    free(pa);
    return 0;
}

Summary

      There are many algorithms for each problem , We should open our minds , Continue to worry about your own algorithm , I will also have a different harvest .