题解 | #二维数组中的查找#

时间复杂度O(m+n) 遍历每一行每一列的右上角元素直到找到元素
无额外空间
利用其有序递增的特点，进行一次循环排除一行或者一列，直到找到元素或者边界
有m行n列，最坏情况下共排除m+n次

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
      if (array.empty() || array[0].empty()) {
        return false;
      }
        
      // 求解行数 列数，以及一个指向右上角的坐标
      int rows = array.size(), columns = array[0].size();
      int row = 0, col = columns - 1;
      
      while (row < rows && col >= 0) {
        if (array[row][col] == target) {
          return true;
        } else if (array[row][col] < target) {
          row++;
        } else if (array[row][col] > target) {
          col--;
        }
      }
      
      return false;
    }
};