我要招人

去企业版

首页 > 试题广场 >

矩阵查找

[编程题]矩阵查找

热度指数：20070 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：

每一行的数字都从左到右排序

每一行的第一个数字都比上一行最后一个数字大

例如：

对于下面的矩阵：

[
    [1,   3,  5,  9],
    [10, 11, 12, 30],
    [230, 300, 350, 500]
]

要搜索的目标值为3，返回true；

示例1

输入

[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],3

输出

true

算法知识视频讲解

Java

JavaEdge

        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)

Java

菜机不配有offer

public boolean searchMatrix (int[][] matrix, int target) {

// write code here

//由于是严格增长，所以可以先进行列二分，再行二分

//这里推荐去做一下leetcode关于二分查找的专版教学题

int hend = matrix.length-1;
int lend = matrix[0].length-1;
int hbegin = 0;

int lbegin = 0;

//从列开始二分搜索

while(hbegin+1<hend){
int mid = hbegin+(hend-hbegin)/2;
if(matrix[mid][0]==target){
return true;

}else if(matrix[mid][0]<target){

//注意这里不是mid+1,因为target可能在mid这一行

hbegin = mid;
}else{
hend = mid-1;
}

}

//定位到行以后再来一遍二分搜索

while(lbegin<lend){
int mid = lbegin+(lend-lbegin)/2;
if(matrix[hbegin][mid]==target){
return true;
}else if(matrix[hbegin][mid]<target){
lbegin = mid+1;
}else{
lend = mid -1;
}
}
return matrix[hbegin][lbegin]==target;
}

发表于 2021-03-17 16:03:01 回复(0)

Java

六娃lw

索然无味，直接二分法就好了

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)

Java

Double厚

算法：

从右上角开始找，左边的都是比它小的，下边的都是比它大的。

如果当前元素等于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)

Java

whynotybb

    int rows = matrix.length;
    int cols = matrix[0].length;
    int i=0,j=cols-1;
    while (i<rows&&j>=0){
        if(matrix[i][j]==target)
            return true;
        if (matrix[i][j]<target){
            i++;
        }
        else {
            j--;
        }
    }
    return false;

发表于 2019-07-24 15:01:48 回复(0)

Java

齐鱼鱼

    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length,n=matrix[0].length;
        int i=m-1,j=0;
        while(i>=0&&j<n){
            if(matrix[i][j]==target)return true;
            else if(matrix[i][j]>target){
                i--;
            }else{
                j++;
            }
        }
        return false;
    }

weiyigenvhaishuati

发表于 2018-09-09 16:20:05 回复(0)

Java

放学后我不走~

先找到行，再找列。

找行：第一行开始，对比每一行的最后一个元素，小于等于该元素则找到行，若无，则返回false

确定行之后：从该行第一个元素开始，对比到最后一个，找到了直接返回true，若无，循环结束返回false

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null || matrix.length<=0 )  return false;    int row = matrix.length;    int lie = matrix[0].length;    int i;    for(i=0;i<row;i++)    if(matrix[i][lie-1]>=target)    break;
        if(i>=row)  return false;    for(int j=0;j<lie;j++)    if(matrix[i][j]==target)    return true;    return false;
    }
}

编辑于 2018-08-31 19:34:29 回复(0)

Java

七仔0312

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0)
            return false;
        int m = matrix.length;
        int n = matrix[0].length;

        return find(matrix, 0, m * n - 1, n, target);
    }

    private boolean find(int[][] matrix, int low, int high, int col, int target) {
        while (low <= high) {
            int mid = (low + high) / 2;
            int x = mid / col;
            int y = mid % col;
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}

发表于 2018-04-02 18:28:43 回复(0)

Java

城市里的养猫者


	
	
		
		
			
/**
 *  Do binary search in this "ordered" matrix
 */ public boolean searchMatrix(int[][] matrix, int target) { int row_num = matrix.length; int col_num = matrix[0].length; int begin = 0, end = row_num * col_num - 1; while(begin <= end){ int mid = (begin + end) / 2; int mid_value = matrix[mid/col_num][mid%col_num]; if( mid_value == target){ return true;
		
		}else if(mid_value < target){ //Should move a bit further, otherwise dead loop. begin = mid+1;
		}else{ end = mid-1;
		}
	} return false;
}
		
		
			More...

发表于 2017-03-12 12:00:01 回复(0)

Java

詆調壹點

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)