【力扣】74. 搜索二維矩陣
給你一個滿足下述兩條屬性的 m x n 整數(shù)矩陣：
- 每行中的整數(shù)從左到右按非遞減順序排列。
- 每行的第一個整數(shù)大于前一行的最后一個整數(shù)。
給你一個整數(shù) target ，如果 target 在矩陣中，返回 true ；否則，返回 false 。
示例 1：
| 1 | 3 | 5 | 7 |
|---|---|---|---|
| 10 | 11 | 16 | 20 |
| 23 | 30 | 34 | 60 |
輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
輸出：true
示例 2：
| 1 | 3 | 5 | 7 |
|---|---|---|---|
| 10 | 11 | 16 | 20 |
| 23 | 30 | 34 | 60 |
輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
輸出：false
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-
1
0
4
10^4
104 <= matrix[i][j], target <=
1
0
4
10^4
104文章來源：http://www.zghlxwxcb.cn/news/detail-608801.html
題解
二分法改進，將二維數(shù)組映射為一維數(shù)組進行二分法文章來源地址http://www.zghlxwxcb.cn/news/detail-608801.html
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
int row = matrix.length;
int col = matrix[0].length;
int left = 0;
int right = row * col - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// (x,y) --> x*col+y
//反過來：一維轉(zhuǎn)二維：matrix[mid/col][mid%col]
int element = matrix[mid / col][mid % col];
if (element == target) {
return true;
}
else if (element > target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return false;
}
}
到了這里，關(guān)于【力扣】74. 搜索二維矩陣 ＜二分法＞的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
