240. Search a 2D Matrix II

三刷 07/2022

Version #1 Iteration

第一个想法是binary search

后来发现是不对的，因为并不是整体有序的，row更小的行有可能包含比下面的row更大的数

Time O(M + N)

Space O(1)

Runtime: 9 ms, faster than 80.42% of Java online submissions for Search a 2D Matrix II.

Memory Usage: 57.6 MB, less than 60.49% of Java online submissions for Search a 2D Matrix II.

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

二刷
if the target is greater than the value in current position, then the target can not be in entire row of current position because the row is sorted, if the target is less than the value in current position, then the target can not in the entire column because the column is sorted too. We can rule out one row or one column each time, so the time complexity is O(m+n).
17.19 %
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) { return false; } // Search from left bottom int row = matrix.length - 1; int col = 0; while (row >= 0 && col < matrix[0].length) { if (matrix[row][col] == target) { return true; } else if (matrix[row][col] > target) { row--; } else { col++; } } return false; } }
一刷
public class Solution {

   public boolean searchMatrix(int[][] matrix, int target) {

       if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {

return false;

}

int rows = matrix.length;

int cols = matrix[0].length;

int x = rows - 1;

int y = 0;

while (x >= 0 && y < cols) {

if (matrix[x][y] == target) return true;

if (matrix[x][y] < target) {

y++;

} else {

x--;

}

}

return false;

   }

}