Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/74.html
You are given an m x n
integer matrix matrix
with the following two properties:
- Each row is sorted in non-decreasing order.
- The first integer of each row is greater than the last integer of the previous row.
Given an integer target
, return true
if target
is in matrix
or false
otherwise.
You must write a solution in O(log(m * n))
time complexity.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
Algorithm
It is also possible to use double pointers, i
points to 0, j
points to the number of columns, so the first number to be verified is the number in the upper right corner of the two-dimensional array.
- If this number is equal to target, return true directly;
- if it is greater than target, it means to decrease For small numbers, the number of columns
j
will decrease by 1; - if it is less than target, it means that the number should be increased, and the number of rows
i
will increase by 1. - If the while loop exits and the target is not found, return false directly
Note
Tried two options:
- The diagonal line from the upper left to the lower right is the baseline to find, because this diagonal is the CLP after the matrix is flattened into a sorted list. But no, moving
row+1
orcol-1
will skip possible targets - Then I tried again. The first column is a binary search first, and then a binary search of the target row. Similarly, some targets may be skipped, when the pointer is +1 or -1
The key is to find a turning point, a certain point, the front is smaller than him, and the back is bigger than him: in this question, it is the point in the upper right corner.
The same is true for the lower left corner.
Code
-
public class Search_a_2D_Matrix { class Solution_binarySearch { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } int left = 0, right = matrix.length; while (left < right) { int mid = (left + right) / 2; if (matrix[mid][0] == target) return true; if (matrix[mid][0] < target) left = mid + 1; else right = mid; } int tmp = (right > 0) ? (right - 1) : right; left = 0; right = matrix[tmp].length; while (left < right) { int mid = (left + right) / 2; if (matrix[tmp][mid] == target) return true; if (matrix[tmp][mid] < target) left = mid + 1; else right = mid; } return false; } } public class Solution { public boolean searchMatrix(int[][] m, int target) { if (m == null || m.length == 0) return false; if (m[0].length == 0) return false; // start from top right int i = 0, j = m[0].length - 1; while (i < m.length && j >= 0) { if (target > m[i][j]) i++; else if (target < m[i][j]) j--; else return true; } return false; } } } ############ class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int left = 0, right = m * n - 1; while (left < right) { int mid = (left + right) >> 1; int x = mid / n, y = mid % n; if (matrix[x][y] >= target) { right = mid; } else { left = mid + 1; } } return matrix[left / n][left % n] == target; } }
-
// OJ: https://leetcode.com/problems/search-a-2d-matrix/ // Time: O(log(MN)) // Space: O(1) class Solution { public: bool searchMatrix(vector<vector<int>>& A, int target) { if (A.empty() || A[0].empty()) return false; int L = 0, R = A.size() - 1; while (L <= R) { int M = (L + R) / 2; if (A[M][0] == target) return true; if (A[M][0] < target) L = M + 1; else R = M - 1; } if (R == -1) return false; int row = R; L = 0, R = A[0].size() - 1; while (L <= R) { int M = (L + R) / 2; if (A[row][M] == target) return true; if (A[row][M] < target) L = M + 1; else R = M - 1; } return false; } };
-
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m, n = len(matrix), len(matrix[0]) left, right = 0, m * n - 1 while left <= right: mid = (left + right) >> 1 x, y = divmod(mid, n) # note: divide column count if matrix[x][y] == target: return True elif matrix[x][y] > target: right = mid - 1 else: left = mid + 1 return False ########### class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m, n = len(matrix), len(matrix[0]) left, right = 0, m * n - 1 while left < right: mid = (left + right) >> 1 x, y = divmod(mid, n) if matrix[x][y] >= target: right = mid else: left = mid + 1 return matrix[left // n][left % n] == target ############ class Solution(object): def searchMatrix(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ if len(matrix) == 0 or len(matrix[0]) == 0: return False m = len(matrix) n = len(matrix[0]) start, end = 0, m * n - 1 while start + 1 < end: mid = start + (end - start) / 2 if matrix[mid / n][mid % n] > target: end = mid elif matrix[mid / n][mid % n] < target: start = mid else: return True if matrix[start / n][start % n] == target: return True if matrix[end / n][end % n] == target: return True return False
-
func searchMatrix(matrix [][]int, target int) bool { m, n := len(matrix), len(matrix[0]) left, right := 0, m*n-1 for left < right { mid := (left + right) >> 1 x, y := mid/n, mid%n if matrix[x][y] >= target { right = mid } else { left = mid + 1 } } return matrix[left/n][left%n] == target }
-
function searchMatrix(matrix: number[][], target: number): boolean { const m = matrix.length; const n = matrix[0].length; let left = 0; let right = m * n; while (left < right) { const mid = (left + right) >>> 1; const i = Math.floor(mid / n); const j = mid % n; if (matrix[i][j] === target) { return true; } if (matrix[i][j] < target) { left = mid + 1; } else { right = mid; } } return false; }
-
/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ var searchMatrix = function (matrix, target) { const m = matrix.length, n = matrix[0].length; let left = 0, right = m * n - 1; while (left < right) { const mid = (left + right + 1) >> 1; const x = Math.floor(mid / n); const y = mid % n; if (matrix[x][y] <= target) { left = mid; } else { right = mid - 1; } } return matrix[Math.floor(left / n)][left % n] == target; };
-
use std::cmp::Ordering; impl Solution { pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool { let m = matrix.len(); let n = matrix[0].len(); let mut i = 0; let mut j = n; while i < m && j > 0 { match matrix[i][j - 1].cmp(&target) { Ordering::Equal => return true, Ordering::Less => i += 1, Ordering::Greater => j -= 1, } } false } }
Algorithm - binary search
Since the matrix is sorted ascending in each row, and the first integer of each row is greater than the last integer of the previous row, the m x n matrix can be reshaped to a 1D array
, where each row is concatenated after the previous row, and binary search can be done on the 1D array.
In practice, the reshape procedure is not necessary and only the idea needs to be used. Initially, set low
to be 0 and high
to be m x n - 1
. The loop condition is low <= high
. Each time, select mid
to be the average of low
and high
, find the row and the column according to mid
, and check the number. The rest procedure is the same as binary search.
-
class Solution_2d_to_1d { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; int rows = matrix.length; int columns = matrix[0].length; int low = 0; int high = rows * columns - 1; while (low <= high) { int mid = (high - low) / 2 + low; int num = matrix[mid / columns][mid % columns]; if (num == target) return true; else if (num > target) high = mid - 1; else low = mid + 1; } return false; } } ############ class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int left = 0, right = m * n - 1; while (left < right) { int mid = (left + right) >> 1; int x = mid / n, y = mid % n; if (matrix[x][y] >= target) { right = mid; } else { left = mid + 1; } } return matrix[left / n][left % n] == target; } }
-
// OJ: https://leetcode.com/problems/search-a-2d-matrix/ // Time: O(log(MN)) // Space: O(1) class Solution { public: bool searchMatrix(vector<vector<int>>& A, int target) { if (A.empty() || A[0].empty()) return false; int L = 0, R = A.size() - 1; while (L <= R) { int M = (L + R) / 2; if (A[M][0] == target) return true; if (A[M][0] < target) L = M + 1; else R = M - 1; } if (R == -1) return false; int row = R; L = 0, R = A[0].size() - 1; while (L <= R) { int M = (L + R) / 2; if (A[row][M] == target) return true; if (A[row][M] < target) L = M + 1; else R = M - 1; } return false; } };
-
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m, n = len(matrix), len(matrix[0]) left, right = 0, m * n - 1 while left <= right: # must be <=, not <, for matrax=[[1]],target=1 mid = (left + right) >> 1 x, y = divmod(mid, n) # note: divide column count if matrix[x][y] == target: return True elif matrix[x][y] > target: right = mid - 1 else: left = mid + 1 return False ############ class Solution(object): def searchMatrix(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ if len(matrix) == 0 or len(matrix[0]) == 0: return False m = len(matrix) n = len(matrix[0]) start, end = 0, m * n - 1 while start + 1 < end: mid = start + (end - start) / 2 if matrix[mid / n][mid % n] > target: end = mid elif matrix[mid / n][mid % n] < target: start = mid else: return True if matrix[start / n][start % n] == target: return True if matrix[end / n][end % n] == target: return True return False
-
func searchMatrix(matrix [][]int, target int) bool { m, n := len(matrix), len(matrix[0]) left, right := 0, m*n-1 for left < right { mid := (left + right) >> 1 x, y := mid/n, mid%n if matrix[x][y] >= target { right = mid } else { left = mid + 1 } } return matrix[left/n][left%n] == target }
-
function searchMatrix(matrix: number[][], target: number): boolean { const m = matrix.length; const n = matrix[0].length; let left = 0; let right = m * n; while (left < right) { const mid = (left + right) >>> 1; const i = Math.floor(mid / n); const j = mid % n; if (matrix[i][j] === target) { return true; } if (matrix[i][j] < target) { left = mid + 1; } else { right = mid; } } return false; }
-
/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ var searchMatrix = function (matrix, target) { const m = matrix.length, n = matrix[0].length; let left = 0, right = m * n - 1; while (left < right) { const mid = (left + right + 1) >> 1; const x = Math.floor(mid / n); const y = mid % n; if (matrix[x][y] <= target) { left = mid; } else { right = mid - 1; } } return matrix[Math.floor(left / n)][left % n] == target; };
-
use std::cmp::Ordering; impl Solution { pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool { let m = matrix.len(); let n = matrix[0].len(); let mut i = 0; let mut j = n; while i < m && j > 0 { match matrix[i][j - 1].cmp(&target) { Ordering::Equal => return true, Ordering::Less => i += 1, Ordering::Greater => j -= 1, } } false } }