- Search a 2D Matrix
Medium
2226167Add to ListShare
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.
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
Example 3:
Input: matrix = [], target = 0
Output: false
Constraints:
m == matrix.length
n == matrix[i].length
0 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
主要代码
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int row = matrix.length;
if (row == 0) {
return false;
}
int col = matrix[0].length;
int len = row * col + 5;
int[] tmp = new int[len];
int k = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
tmp[k++] = matrix[i][j];
}
}
int l = 0, r = k - 1;
while (l < r) {
int mid = (l + r) / 2;
if (tmp[mid] == target) {
return true;
} else if (tmp[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (tmp[l] == target) {
return true;
}
return false;
}
}