Leetcode.240.Search a 2D Matrix

题目

在一个二维数组中寻找指定的数。

[[1,   4,  7, 11, 15],
 [2,   5,  8, 12, 19], 
 [3,   6,  9, 16, 22],
 [10, 13, 14, 17, 24],
 [18, 21, 23, 26, 30]] 
Input：5
Output：true
Input：20
Output：false

思路

循环。从第一行最后一列，不断缩进行和列，小于就行减减，大于就列加加。

bool searchMatrix(vector<vector<int>>& matrix, int target) {
  if (matrix.empty()) return false;
  int row = 0,col = (int)matrix[0].size()-1;

  while (row < matrix.size() && col >= 0) {
    if (matrix[row][col] == target) {
        return true;
    } else if (matrix[row][col] > target){
        col--;
    } else {
        row++;
    }
  }

  return false;
}

总结

也可以递归，采用二分法分别确定行和列的最大值和最小值，但是时间复杂度和空间复杂度都不太理想。