Tag:Lintcode C++ matrix
Category:Lintcode
Article From:https://www.cnblogs.com/Tang-tangt/p/9064594.html

Original website: https://www.lintcode.com/zh-cn/old/problem/search-a-2d-matrix-ii/#

38. Search two-dimensional matrix II

 

Discussion area

Write an efficient algorithm to search the values in the m x n matrix and return the number of times that value occurs.

This matrix has the following properties:

 

  • The integers in each line are sorted from left to right.
  • The integers in each column are sorted from top to bottom.
  • There are no repeating integers in every row or column.

 

Sample

Consider the following matrix:

[

    [1, 3, 5, 7],

    [2, 4, 7, 8],

    [3, 5, 9, 10]

]

Give target = =3,Return 2

Challenge 

O (m+n) time complexity and O (1) extra space

Label 

Amazon Sorted Matrix Google apple
 
Unchallenged version of the idea:
Brain donkey, see sorting array (matrix) search problem first thought is two points search method…… For each row, two points search statistics are made, and the time complexity is O (m * log (n)).
ACCode:
class Solution {
public:
    /**
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    int searchMatrix(vector<vector<int>> &matrix, int target) {
        // write your code here
        if (matrix.empty())
    {
        return 0;
    }
    int result=0;
    int rowSize=matrix.size();
    int colSize=matrix[0].size();
    if (target<matrix[0][0]||target>matrix[rowSize-1][colSize-1])
    {
        return result;
    }

    for (int i=0;i<rowSize;i++)
    {
        int begin=0,end=colSize-1,mid=begin+end/2;
        while(begin<=end)
        {
            if (target==matrix[i][mid])
            {
                ++result;
                break;
            }
            else if (target<matrix[i][mid])
            {
                end=mid-1;
                mid=(begin+end)/2;
            }
            else 
            {
                begin=mid+1;
                mid=(begin+end)/2;
            }
        }
    }

    return result;
    }
};

Challenge:

https://www.cnblogs.com/edisonchou/p/4737944.html   You can see more than a few times

https://blog.csdn.net/ljlstart/article/details/48517509

Using the characteristics of a given matrix, it can go from the upper right corner to the lower left corner, or from the lower left corner to the upper right corner. In this way, the current row is removed or the current column is removed.

First, if the current point is greater than target, the current column -1 is to determine matrix [row] [COL-1];

If the current point is less than target, the current row +1 is to determine matrix [row+1] [col];

If the current point is equal to target, the counter adds 1, then the current row +1, the current column -1;

Repeat the above steps until the lower left corner.

ACCode:

class Solution {
public:
    /**
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    int searchMatrix(vector<vector<int>> &matrix, int target) {
        // write your code here
        if (matrix.empty())
    {
        return 0;
    }
    int result=0;
    int rowSize=matrix.size();
    int colSize=matrix[0].size();
    if (target<matrix[0][0]||target>matrix[rowSize-1][colSize-1])
    {
        return result;
    }
    int i=0,j=colSize-1;
    while(i>=0&&i<rowSize&&j>=0&&j<colSize)
    {
        if (matrix[i][j]==target)
        {
            ++result;
                ++i;
                --j;    
        }
        else if (matrix[i][j]<target)
        {
            ++i;
            
        }
        else
        {
            --j;
        }
    }
    return result;
    }
};

 

Link of this Article: 38 search two-dimensional matrix II

Leave a Reply

Your email address will not be published. Required fields are marked *