Easy C++ 12ms O(N) Solution. Not using a Binary Search


  • 0
    B
    1. let me set m to be the rows of the matrix and n to be the cols of the matrix.
    2. set i = 0 and j = n-1. then, matrix[i][j] = matrix[0][n-1], this element is located in the upper right corner of the matrix.
    3. if target == matrix[i][j], then return true;

    if target > matrix[i][j], because matrix[i][j] is the largest element of row i, target is larger than all the element in row i. DO. i++;

    if target < matrix[i][j], because matrix[i][j] is the minimum element of col j, target is smaller than all the element in col j. DO. j--

    1. if i > m - 1 or j < 0, break the while loop, and return false;

    coding:

    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if(matrix.size() == 0)  return false;
    	    int m = matrix.size();
    	    int n = matrix[0].size();
    	    int i = 0, j = n-1;
    	    while(i < m && j >= 0){
    	        if(matrix[i][j] == target)
    	            return true;
    	        else if(matrix[i][j] < target)
    	    	    ++i;
    	        else
    		        --j;	
    	    }
    	    return false;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.