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,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
題目
寫出一個高效的算法來搜索 m × n矩陣中的值处嫌。
這個矩陣具有以下特性：
- 每行中的整數(shù)從左到右是排序的稽寒。
- 每行的第一個數(shù)大于上一行的最后一個整數(shù)翔横。
樣例
考慮下列矩陣：
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
給出 target = 3，返回 true
分析
本題主要考察的是二分法或详，但是這里如何使用二分法又有不同的策略，但本質(zhì)都是一樣的
方法一胜臊，我們二分问麸，先從每列的最后一個數(shù)開始，確定它的列再搜索行
方法二阵谚，就是將二維數(shù)組展開一維數(shù)組蚕礼，然后二分法中間的數(shù)
方法三烟具，就是分別求行和列，求行時奠蹬，用二分法净赴，然后求列在用二分法。
代碼
方法一
public class Solution {
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
public boolean searchMatrix(int[][] matrix, int target) {
// write your code here
if(matrix == null)
return false;
int rows=matrix.length;
if(rows == 0 )
return false;
// 行數(shù)
int cols=matrix[0].length; // 列數(shù)
int i=0, j=cols-1;
boolean found = false;
while(j>=0 && j<cols && i<rows) // i>=0 默認滿足罩润，無須再判斷
{
if(matrix[i][j] == target) { found = true; break; }
else if(matrix[i][j] > target) j--; // 如果矩陣右上角的值比target大，刪除所在的列翼馆，列號-1
else i++; // 如果矩陣右上角的值不大于target割以，刪除所在的行，行號+1
}
return found;
}
}
方法二
public class Solution {
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
public boolean searchMatrix(int[][] matrix, int target) {
// write your code here
if (matrix == null || matrix.length == 0) {
return false;
}
if (matrix[0] == null || matrix[0].length == 0) {
return false;
}
int row = matrix.length, column = matrix[0].length;
int start = 0, end = row * column - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
int number = matrix[mid / column][mid % column];
if (number == target) {
return true;
} else if (number < target) {
start = mid;
} else {
end = mid;
}
}
if (matrix[start / column][start % column] == target) {
return true;
} else if (matrix[end / column][end % column] == target) {
return true;
}
return false;
}
}
方法三
public class Solution {
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
public boolean searchMatrix(int[][] matrix, int target) {
// write your code here
if (matrix == null || matrix.length == 0) {
return false;
}
if (matrix[0] == null || matrix[0].length == 0) {
return false;
}
int row = matrix.length;
int column = matrix[0].length;
// find the row index, the last number <= target
int start = 0, end = row - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (matrix[mid][0] == target) {
return true;
} else if (matrix[mid][0] < target) {
start = mid;
} else {
end = mid;
}
}
if (matrix[end][0] <= target) {
row = end;
} else if (matrix[start][0] <= target) {
row = start;
} else {
return false;
}
// find the column index, the number equal to target
start = 0;
end = column - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (matrix[row][mid] == target) {
return true;
} else if (matrix[row][mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (matrix[row][start] == target) {
return true;
} else if (matrix[row][end] == target) {
return true;
}
return false;
}
}
