Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/74.html
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,
Example 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
@tag-array
@tag-binarysearch
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
jwill decrease by 1; - if it is less than target, it means that the number should be increased, and the number of rows
iwill 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+1orcol-1will 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
Java
-
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; } } } -
// 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) 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
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; } } -
// 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) 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