【杂题】剑指 Offer 04. 二维数组中的查找-跟着帅地玩副业，开拓第二曲线PlayOffer

CrazyJavaBoy 永久会员 2023年3月24日上午9:32

从左下角开始往右上角开始找

利用行列的非递减特点

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        //rows表示行
        int rows = matrix.length;
        //cols表示列
        int cols = matrix[0].length;

        //从左下角开始 往右上角遍历
        int row = rows - 1;;//从最后一行开始
        int col = 0;//从第一列开始

        while(row >= 0 && col < cols) {
            if(matrix[row][col] > target) {//当前值大于target 消除最后一行 
                row --;    
            } else if(matrix[row][col] < target) {//当前值小于最后一行 消除最左一列
                col ++;
            } else {//相等了 直接返回存在
                return true; 
            }
        }
        return false;
    }
}

0 赞同 0 条回复

宁永久会员 2023年3月14日下午7:25

从左下角或者右上角算起

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        //从左下角或者右上角开始算起，移动方向唯一确定
        int row = matrix.length - 1;
        int col = 0;
        while(col < matrix[0].length && row >= 0){
            if(target > matrix[row][col]){
                col++;
            } else if(target < matrix[row][col]){
                row--;
            }else{
                return true;
            }
        }
        return false;
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月17日下午11:48

二分

取右上节点，如果比目标值小就下移，如果比目标值大就左移
保证每次都可以至少舍弃一行或一列
最坏情况从右上遍历到坐下
时间复杂度O(M+N)
空间复杂度O(1)

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

0 赞同 0 条回复

T 普通 2022年12月3日上午10:02

下面代码

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

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

0 赞同 0 条回复

青木普通 2022年12月2日下午9:19

/**
    只能想到方阵的优化，直接按对角线遍历，找到第一个大于target的数，然后继续遍历这个数所在行和列就可以了
    但是由于题目是矩阵，可惜没想出来

    题解的优化就是从左下开始，每次可以干掉一行或者一列

    时间O(m + n)
    空间O(1)
 */

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


/**
    本来以为暴力不能过的，一直在想优化，结果真能过
    时间O(mn)
    空间O(1)
 */

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        for(int i=0; i<matrix.length; i++){
            for(int j=0; j<matrix[0].length; j++){
                if(matrix[i][0] > target) return false;
                if(matrix[i][j] == target) return true;
            }
        }
        return false;
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年12月1日上午11:15

从右上角开始搜索，小于往左，大于往下。时间复杂度O(MN)

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

0 赞同 0 条回复

Mooby 普通 2022年12月1日上午9:33

// 时间复杂度O(m + n)，空间复杂度O(1)
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int cols = matrix.length;
        int rows = matrix[0].length;
        int col = cols - 1;
        int row = 0;
        while (col >= 0 && row < rows) {
            if (target > matrix[col][row]) {
                row++;
            } else if (target < matrix[col][row]) {
                col--;
            } else {
                return true;
            }
        }
        return false;
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月30日下午9:29

时间复杂度为O（n+m），空间复杂度为O（1）

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

}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:40

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        //对每一行进行二分查找
        for(auto& row:matrix){
            auto it = lower_bound(row.begin(),row.end(),target);
            if(it!=row.end()&&*it==target) return true;
        }
        return false;
    }
};

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:40

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        //对每一行进行二分查找
        for(auto& row:matrix){
            auto it = lower_bound(row.begin(),row.end(),target);
            if(it!=row.end()&&*it==target) return true;
        }
        return false;
    }
};

0 赞同 0 条回复

【杂题】剑指 Offer 04. 二维数组中的查找

共以下 10 个回答

从左下角开始往右上角开始找

二分

# 回答此问题取消回复

【杂题】剑指 Offer 04. 二维数组中的查找

共以下 10 个回答

从左下角开始往右上角开始找

二分

# 回答此问题 取消回复

# 回答此问题取消回复