【LeetCode】74. 搜索二维矩阵（Java）

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。

提示：

m == matrix.lengthn == matrix[i].length0 <= m, n <= 100-104 <= matrix[i][j], target <= 104

进阶应该是这道题240. 搜索二维矩阵 II。

解法一

class Solution { public boolean searchMatrix(int[][] matrix, int target) { //二分 int m = matrix.length; if (m == 0) return false; int n = matrix[0].length; if (n == 0) return false; int left = 0, right = m * n - 1; while (left < right) { int mid = left + (right - left) / 2; //n为每一行的长，除以n得到行数，取余n得到行的位数 //取余和普通的二分一样 if (matrix[mid / n][mid % n] < target) { left = mid + 1; } else { right = mid; } } return matrix[left / n][left % n] == target; } }

解法二

class Solution { public boolean searchMatrix(int[][] matrix, int target) { //走图 int col = matrix.length; //列 if (col == 0) return false; int row = matrix[0].length; //行 if (row == 0) return false; //从右上角开始，比目标值大往左走，比目标值小往下走 int h = 0, w = row - 1; //走出边界跳出循环 while (h < col && w >= 0) { if (matrix[h][w] > target) { w--; } else if (matrix[h][w] < target) { h++; } else { return true; } } return false; } }