请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：
每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大
例如：
对于下面的矩阵：
[
[1, 3, 5, 9],
[10, 11, 12, 30],
[230, 300, 350, 500]
] 要搜索的目标值为3，返回true；
[编程题]矩阵查找
首先选取右上角数字，如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，去掉此数字所在列；如果该数字小于要查找的数字，则去掉该数字所在行。重复上述过程直到找到要查找的数字，或者查找范围为空。
bool searchMatrix(vector<vector<int> > &matrix, int target){
int i=0, j=matrix[0].size()-1;
while(i<matrix.size() && j>=0){
if(matrix[i][j]==target){
return true;
}
else if(matrix[i][j]<target){
i++; //去掉这一行
}
else{
j--; //去掉这一列
}
}
return false;
}
发表于 2017-04-18 10:11:07
回复(2)
/*
* 最优解法：Binary search on an ordered matrix
* 二分查找
* Runtime: 0 ms.Your runtime beats 75.27 % of java submissions
*/
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return false;
int m = matrix.length, n = matrix[0].length;
int start = 0, end = m * n - 1;
// 二分查找
while (start <= end) {
int mid = start + (end - start) / 2;
int value = matrix[mid / n][mid % n];
if (target > value) {
start = mid + 1;
} else if (target < value)
end = mid - 1;
else
return true;
}
return false;
}
/*
* 解法二： Solution by me Runtime: 1 ms.Your runtime beats 6.66 % of java
* submissions. 刚开始指向右上角元素，如果target大于该元素，下移；如果target小于该元素，左移；
*/
public boolean searchMatrix_1(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return false;
int m = 0, n = matrix[0].length - 1;
// 避免角标越界
while (m >= 0 && m < matrix.length && n >= 0 && n < matrix[0].length) {
if (target > matrix[m][n])
m++;
else if (target < matrix[m][n])
n--;
else
return true;
}
return false;
}
发表于 2017-06-29 10:42:56
回复(3)
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int rows = matrix.size();
int cols = matrix[0].size();
int begin = 0,end = rows*cols-1;
while(begin <= end)
{
int mid = (begin + end)/2;
int row = mid/cols;
int col = mid%cols;
if(matrix[row][col] == target)
return true;
else if(matrix[row][col] < target)
begin = mid + 1;
else
end = mid - 1;
}
return false;
}
};
发表于 2017-08-02 01:46:19
回复(0)
import java.util.*;
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
return false;
int m = matrix.length;
int n = matrix[0].length;
int head = 0;
int tail = m * n - 1;
while(head <= tail)
{
int mid = (head + tail)/2;
int value = matrix[mid/n][mid%n];
if(target == value)
return true;
if(target > value)
head = mid + 1;
else
tail = mid - 1;
}
return false;
}
}
编辑于 2018-06-24 17:28:23
回复(0)
c++ solution：
class Solution {
public:
bool searchMatrix(vector > &matrix, int target) {
if (matrix.size() == 0 || matrix[0].size()==0) //if there is not element in matrix, return false;
return false;
/**
* search from the top-right, using binary-search
* if current element is larger than the target => row-=1
* if current element is smaller than the target => col+=1
*/
int row = 0;
int col = matrix[0].size()-1;
while (row = 0) {
int cur = matrix[row][col];
if (cur == target)
return true;
else if (cur > target)
col -= 1;
else
row += 1;
}
return false;
}
};
编辑于 2018-09-17 15:02:56
回复(0)
class Solution {
public:
//思路参考的下面分享的答案，把二维的表格看成是一维的数组
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int row = matrix.size();
if(row == 0) return false;
int col = matrix[0].size();
int count = row * col;
int begin = 0;
int end = count-1;
while(begin <= end){
int mid = (begin + end)/2;
int a = mid/col;
int b = mid%col;
if(target == matrix[a][b]) return true;
else if(target >matrix[a][b]) begin = mid +1;
else end = mid -1;
}
return false;
}
};
编辑于 2017-02-24 19:59:13
回复(0)
class Solution {
public:
/**
*
* @param matrix int整型vector<vector<>>
* @param target int整型
* @return bool布尔型
*/
bool searchMatrix(vector<vector<int> >& matrix, int target) {
// write code here
int n = matrix.size() * matrix[0].size();
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
int i = mid / matrix[0].size();
int j = mid % matrix[0].size();
int mid_val = matrix[i][j];
if (mid_val == target) return true;
if (mid_val > target) right = mid - 1;
if (mid_val < target) left = mid + 1;
}
return false;
}
}; 线性有序，转换下下标就行了
发表于 2021-08-13 15:15:39
回复(0)
class Solution {
public:
/**
*
* @param matrix int整型vector<vector<>>
* @param target int整型
* @return bool布尔型
*/
bool searchMatrix(vector<vector<int> >& matrix, int target) {
const int m = matrix.size(), n = matrix[0].size();
int x = n - 1, y = 0;
while (x >= 0 && y < m) {
if (target == matrix[y][x]) return true;
if (target > matrix[y][x]) ++y;
else --x;
}
return false;
}
};
发表于 2021-07-08 16:56:44
回复(0)
索然无味，直接二分法就好了
public class Solution {
/**
*
* @param matrix int整型二维数组
* @param target int整型
* @return bool布尔型
*/
public boolean searchMatrix (int[][] matrix, int target) {
// write code here
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){return false;}
int m = matrix.length, n = matrix[0].length;
int l = 0, r = m * n - 1;
while(l < r){
int mid = l + (r - l) / 2;
int midNum = matrix[mid / n][mid % n];
if(midNum == target){return true;}
else if(midNum < target){l = mid + 1;}
else{r = mid;}
}
return matrix[l / n][l % n] == target;
}
}
编辑于 2020-11-17 22:59:13
回复(0)
算法：
从右上角开始找，左边的都是比它小的，下边的都是比它大的。
如果当前元素等于target，那么说明找到了，返回true；
如果当前元素大于target，那么当前元素下面的一定都比target大，所以左移；
如果当前元素小于target，那么当前元素左面的一定都比target小，所以下移；
如果最后没返回true，则返回false。
时间复杂度：
O( m + n ) m为矩阵的行数，n为矩阵的列数
Code：
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
j--;
} else {
i++;
}
}
return false;
}
编辑于 2020-10-27 18:54:32
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param matrix int整型二维数组
* @param target int整型
* @return bool布尔型
*/
//二分查找
public boolean searchMatrix (int[][] matrix, int target) {
// write code here
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
int m = matrix.length;
int n = matrix[0].length;
int start = 0,end = m*n-1;
while(start <= end){
int mid = (start+end)/2;
int val = matrix[mid/n][mid%n];
if(val < target){
start = mid+1;
}else if (val > target){
end = mid-1;
}else{
return true;
}
}
return false;
}
//普通方案，跑了一次，时间36ms，内存10864KB，接近二分
public boolean searchMatrix1 (int[][] matrix, int target) {
// write code here
//处理了两个边界值，第一个和最后一个元素
if(matrix == null || matrix.length == 0 || matrix[0].length == 0 || target < matrix[0][0]) return false;
int row = -1;
int m = matrix.length;
int n = matrix[0].length;
if(target > matrix[m-1][n-1]) return false;
//找到数据落在的行，可能是边界，如果恰好是边界，就返回
for(int i = 0; i<m; i++){
if(matrix[i][0] == target || matrix[i][n-1] == target) return true;
if(matrix[i][0] < target && matrix[i][n-1] > target) row = i;
}
//遍历对应行所有数据
for(int i = 0; i<n && row >= 0 ; i++){
if(matrix[row][i] == target){
return true;
}
}
return false;
}
}
编辑于 2020-09-08 14:08:46
回复(0)
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int r=matrix.size();
if(r==0)
return false;
int c=matrix[0].size();
for(int i=0;i<r*c;i++){
if(matrix[i/c][i%c]==target)
return true;
if(matrix[i/c][i%c]>target)
return false;
}
return false;
}
};
发表于 2018-06-24 22:43:56
回复(0)
先纵向二分查找，再横向二分查找，复杂度为log(m) + log(n)，
把二维当做一维的二分复杂度为log(n*m)，
双向二分更优；
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int up = 0, down = m - 1, mid = (up + down) / 2;
while(up <= down) {
if(matrix[mid][0] > target) {
// search up
down = mid - 1;
} else if(matrix[mid][n-1] >= target) {
// search in line
break;
} else {
//search down
up = mid + 1;
}
mid = (up + down) / 2;
}
if(up <= down) {
//search in line
int l = 0, r = n - 1;
int [] line = matrix[mid];
mid = (l + r) / 2;
while(l <= r) {
if(line[mid] > target) {
//search left
r = mid - 1;
} else if(line[mid] == target) {
return true;
} else {
//search right
l = mid + 1;
}
mid = (l + r) / 2;
}
return false;
} else {
return false;
}
}
}
发表于 2018-03-05 23:43:25
回复(1)
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int rowLen = matrix.length;
int columnLen = matrix[0].length;
int start = 0, end = rowLen*columnLen-1;
while(start<=end) {
int mid = start+(end-start)/2;
int midVal = matrix[mid/columnLen][mid%columnLen];
if(midVal>target) {
end = mid-1;
} else if(midVal<target){
start=mid+1;
} else {
return true;
}
}
return false;
}
}
发表于 2017-12-03 08:49:57
回复(0)
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int rows=matrix.size();
int cols=matrix[0].size();
if(rows==0)
return false;
int i=0;
int j=cols-1;
while(i<=rows-1&&j>=0){
if(matrix[i][j]==target)
return true;
else if(matrix[i][j]<target)
i++;
else
j--;
}
return false;
发表于 2017-11-06 08:43:03
回复(0)
public class Solution {
public static boolean searchMatrix(int[][] matrix, int target) {
int row = 0;
boolean isFinded = false;
for (int i = 0; i < matrix.length; i ++ ) {
if(target == matrix[i][matrix[0].length - 1]) return true;
else if(target < matrix[i][matrix[0].length - 1]) {
isFinded = true;
row = i;
break;
}
}
if( ! isFinded) return false;
for (int i = 0; i < matrix[0].length; i ++ ) {
if(matrix[row][i] > target) break;
else if(target == matrix[row][i]) return true;
}
return false;
}
}
发表于 2016-11-06 13:47:12
回复(0)
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
//Integers in each row are sorted from left to right.
//所以很容易想到二分查找
int row = matrix.size();
int col = matrix[0].size();
int l=0,h=row*col,m;
while(l<h){
m = l+((h-l)>>1);
int i=m/col;
int j=m%col;
if(matrix[i][j]>target){ //取左区间
h=m;
}else if(matrix[i][j]<target){ //取右区间
l=m+1;
}else{ //等于
return true;
}
}
return false;
}
};
发表于 2016-06-26 22:14:00
回复(0)
/*
思路：排除
右上角数字是本行最大，本列最小。
当右上角大于目标数字，去前一列找。
当右上角小于目标数字，去下一行找。
*/
class Solution {
public:
/**
*
* @param matrix int整型vector<vector<>>
* @param target int整型
* @return bool布尔型
*/
bool searchMatrix(vector<vector<int> >& matrix, int target) {
if(matrix.size()==0){
return false;
}
int i=0;
int j=matrix[0].size()-1;
while(i<matrix.size() && j>=0){
//遇见，直接返回
if(target == matrix[i][j]){
return true;
}
//当前值小于目标
if(target > matrix[i][j]){
i++;
continue;
}
//当前值大于目标
if(target < matrix[i][j]){
j--;
continue;
}
}
return false;
}
};
发表于 2023-04-11 22:26:57
回复(0)
if (matrix.length == 1) {
return Arrays.binarySearch(matrix[0], target) >= 0;
}
for (int i = 0; i < matrix.length; i++) {
if (target < matrix[i][0]) {
// 在上一行
if (i == 0) {
return false;
}
return Arrays.binarySearch(matrix[i - 1], target) >= 0;
} else if (target == matrix[i][0]) {
return true;
}
}
return false;
发表于 2022-02-01 20:18:42
回复(0)
bool searchMatrix(vector<vector<int> >& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int left = 0, right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int i = mid / n, j = mid % n;
if (matrix[i][j] == target) return true;
if (matrix[i][j] > target) right = mid - 1;
else left = mid + 1;
}
return false;
}
发表于 2021-07-25 16:51:59
回复(0)
问题信息
难度：
93条回答
79收藏
27520浏览
通过挑战的用户
查看代码-
2023-02-13 19:48:15
-
2023-02-13 15:13:40 -
2022-12-30 09:53:27
-
2022-10-04 17:08:35 -
2022-09-21 01:59:28
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
