Linux Access the Open Internet

240.搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性： 每行的元素从左到右升序排列。每列的元素从上到下升序排列

示例 1：输入：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]], target = 5 输出：true

示例 2：输入：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]], target = 20 输出：false

分析:
1.二维矩阵搜索, 其实这个搜索也是有序的, 从上到下, 从左往右有序, 最小的永远在左上角, 最大的永远在右下角, 但是右上角和左下角哪个更大我们不知道
2.最基础的方法可以对逐行进行二分搜索, 每一行是 logn复杂度, 总时间复杂度 nlogn

class Solution {
 public:
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rowNum = matrix.size();
    for (int row = 0; row < rowNum; ++row) {
      if (binary_search(matrix[row].begin(), matrix[row].end(), target)) {
        return true;
      }
    }
    return false;
  }
};

3.这个矩阵的特点我们得充分利用下, 因为右边总比左边大, 下边总比上边大, 我们可以先卡一个最大的子坐标, 另一个从 0 开始搜索, 比如从右上角 (0, n - 1) 元素开始搜索, 如果当前搜索元素比目标元素小, 那么就往下搜索, 纵坐标不动; 如果当前搜索元素比目标元素大, 那么就缩小右边界

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

---

转载请注明来源 goldandrabbit.github.io