题目描述（中等难度）

240. Search a 2D Matrix II - 图1

矩阵的每行从左到右是升序， 每列从上到下也是升序，在矩阵中查找某个数。

解法一

看到有序，第一反应就是二分查找。最直接的做法，一行一行的进行二分查找即可。

此外，结合有序的性质，一些情况可以提前结束。

比如某一行的第一个元素大于了 target ，当前行和后边的所有行都不用考虑了，直接返回 false。

某一行的最后一个元素小于了 target ，当前行就不用考虑了，换下一行。

  1. public boolean searchMatrix(int[][] matrix, int target) {
  2.     if (matrix.length == 0 || matrix[0].length == 0) {
  3.         return false;
  4.     }
  5.     for (int i = 0; i < matrix.length; i++) {
  6.         if (matrix[i][0] > target) {
  7.             break;
  8.         }
  9.         if(matrix[i][matrix[i].length - 1] < target){
  10.             continue;
  11.         } 
  12.         int col = binarySearch(matrix[i], target);
  13.         if (col != -1) {
  14.             return true;
  15.         }
  16.     }
  17.     return false;
  18. }
  20. //二分查找
  21. private int binarySearch(int[] nums, int target) {
  22.     int start = 0;
  23.     int end = nums.length - 1;
  24.     while (start <= end) {
  25.         int mid = (start + end) >>> 1;
  26.         if (nums[mid] == target) {
  27.             return mid;
  28.         } else if (nums[mid] < target) {
  29.             start = mid + 1;
  30.         } else {
  31.             end = mid - 1;
  32.         }
  33.     }
  34.     return -1;
  35. }

时间复杂度的话，如果是 m 行 n 列，就是 O(mlog(n))。

解法二

参考 这里-Java-solution)，需要很敏锐的观察力了。

数组从左到右和从上到下都是升序的，如果从右上角出发开始遍历呢？

会发现每次都是向左数字会变小，向下数字会变大，有点和二分查找树相似。二分查找树的话，是向左数字变小，向右数字变大。

所以我们可以把 target 和当前值比较。

  • 如果 target 的值大于当前值，那么就向下走。
  • 如果 target 的值小于当前值，那么就向左走。
  • 如果相等的话，直接返回 true 。

也可以换个角度思考。

如果 target 的值小于当前值，也就意味着当前值所在的列肯定不会存在 target 了，可以把当前列去掉，从新的右上角的值开始遍历。

同理，如果 target 的值大于当前值，也就意味着当前值所在的行肯定不会存在 target 了，可以把当前行去掉，从新的右上角的值开始遍历。

看下边的例子。

  1. [1,   4,  7, 11, 15],
  2. [2,   5,  8, 12, 19],
  3. [3,   6,  9, 16, 22],
  4. [10, 13, 14, 17, 24],
  5. [18, 21, 23, 26, 30]
  7. 如果 target  = 9，如果我们从 15 开始遍历, cur = 15
  9. target < 15, 去掉当前列, cur = 11
  10. [1,   4,  7, 11],
  11. [2,   5,  8, 12],
  12. [3,   6,  9, 16],
  13. [10, 13, 14, 17],
  14. [18, 21, 23, 26]    
  16. target < 11, 去掉当前列, cur = 7  
  17. [1,   4,  7],
  18. [2,   5,  8],
  19. [3,   6,  9],
  20. [10, 13, 14],
  21. [18, 21, 23]     
  23. target > 7, 去掉当前行, cur = 8   
  24. [2,   5,  8],
  25. [3,   6,  9],
  26. [10, 13, 14],
  27. [18, 21, 23]       
  29. target > 8, 去掉当前行, cur = 9, 遍历结束    
  30. [3,   6,  9],
  31. [10, 13, 14],
  32. [18, 21, 23]

不管从哪种角度考虑，代码的话都是一样的。

  1. public boolean searchMatrix(int[][] matrix, int target) {
  2.     if (matrix.length == 0 || matrix[0].length == 0) {
  3.         return false;
  4.     }
  5.     int row = 0;
  6.     int col = matrix[0].length - 1;
  7.     while (row < matrix.length && col >= 0) {
  8.         if (target > matrix[row][col]) {
  9.             row++;
  10.         } else if (target < matrix[row][col]) {
  11.             col--;
  12.         } else {
  13.             return true;
  14.         }
  15.     }
  16.     return false;
  17. }

时间复杂度就是每个节点最多遍历一遍了，O(m + n)。

解法三

参考 这里 ，还有一种解法。

我的理解的话，算是一种变形的二分法。

二分法的思想就是，目标值和中点值进行比较，然后可以丢弃一半的元素。

这道题的话是矩阵，如果我们找到矩阵的中心，然后和目标值比较看能不能丢弃一些元素。

  1. 如下图，中心位置是 9
  2. [1,   4,  7, 11, 15],
  3. [2,   5,  8, 12, 19],
  4. [3,   6, /9/,16, 22],
  5. [10, 13, 14, 17, 24],
  6. [18, 21, 23, 26, 30]
  8. 通过中心位置, 我们可以把原矩形分成四个矩形, 左上, 右上, 左下, 右下
  9. [1,   4,  7   [11, 15  
  10.  2,   5,  8    12, 19  
  11.  3,   6, /9/]  16, 22] 
  13. [10, 13, 14   [17, 24
  14. [18, 21, 23]   26, 30]
  16. 如果 target = 10,
  17. 此时中心值小于目标值，左上角矩形中所有的数都小于目标值，我们可以丢弃左上角的矩形，继续从剩下三个矩形中寻找
  19. 如果 target = 5,
  20. 此时中心值大于目标值，右下角矩形中所有的数都大于目标值，那么我们可以丢弃右下角的矩形，继续从剩下三个矩形中寻找

我们找到了丢弃元素的原则，可以写代码了。

这里的话，矩形我们用左上角和右下角坐标的形式表示，下图是分割后矩形的坐标情况。

240. Search a 2D Matrix II - 图2

我们可以用递归的形式去写，递归出口的话，当矩阵中只有一个元素，直接判断当前元素是不是目标值即可。

还有就是分割的时候可能越界，比如原矩阵只有一行，左下角和右下角的矩阵其实是不存在的，按照上边的坐标公式计算出来后，我们要判断一下是否越界。

  1. public boolean searchMatrix(int[][] matrix, int target) {
  2.     if (matrix.length == 0 || matrix[0].length == 0) {
  3.         return false;
  4.     }
  5.     return searchMatrixHelper(matrix, 0, 0, matrix[0].length - 1, matrix.length - 1, matrix[0].length - 1, matrix.length - 1, target);
  6. }
  8. private boolean searchMatrixHelper(int[][] matrix, int x1, int y1, int x2, int y2, int xMax, int yMax, int target) {
  9.     //只需要判断左上角坐标即可
  10.     if (x1 > xMax || y1 > yMax) {
  11.         return false;
  12.     }
  14.     //x 轴代表的是列，y 轴代表的是行
  15.     if(x1 == x2 && y1 == y2){
  16.         return matrix[y1][x1] == target;
  17.     }
  18.     int m1 = (x1 + x2) >>> 1;
  19.     int m2 = (y1 + y2) >>> 1;
  20.     if (matrix[m2][m1] == target) {
  21.         return true;
  22.     }
  23.     if (matrix[m2][m1] < target) {
  24.         // 右上矩阵
  25.         return searchMatrixHelper(matrix, m1 + 1, y1, x2, m2, x2, y2, target) ||
  26.             // 左下矩阵
  27.             searchMatrixHelper(matrix, x1, m2 + 1, m1, y2, x2, y2, target) ||
  28.             // 右下矩阵
  29.             searchMatrixHelper(matrix, m1 + 1, m2 + 1, x2, y2, x2, y2, target);
  31.     } else {
  32.         // 右上矩阵
  33.         return searchMatrixHelper(matrix, m1 + 1, y1, x2, m2, x2, y2, target) ||
  34.             // 左下矩阵
  35.             searchMatrixHelper(matrix, x1, m2 + 1, m1, y2, x2, y2, target) ||
  36.             // 左上矩阵
  37.             searchMatrixHelper(matrix, x1, y1, m1, m2, x2, y2, target);
  38.     }
  39. }

总

看到有序数组第一反应就是二分了，也就是解法一。

解法二的话，从右上角开始遍历的想法很妙。

解法三的话思想很简单，就是变形的二分法，每次抛弃一部分元素，但代码的话其实写出来不是很容易，相对于解法一和解法二来说是有些复杂度的。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情