Leetcode 240. Search a 2D Matrix II

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

• O(mlogn)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        if(rows == 0) {
            return false;
        }
        int columns = matrix[0].size();
        if(columns == 0) {
            return false;
        }
        for(int i = 0; i < rows; i++) {
            int left = 0;
            int right = columns - 1;
            while(left <= right) {
                int middle = (left + right) >> 1;
                if(target == matrix[i][middle]) {
                    return true;
                }
                else if(target > matrix[i][middle]) {
                    left = middle + 1;
                }
                else {
                    right = middle - 1;
                }
            }
        }
        return false;
    }
};

• O(m+n)

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

• or

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

Reference

1. https://leetcode.com/problems/search-a-2d-matrix-ii/description/