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

本问题对应课程链接：剑指offer刷题第三期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 3 年前 147 9

共以下 9 个回答

九号球普通 2023年12月6日下午10:20

“`java
class Solution {
public boolean findTargetIn2DPlants(int[][] plants, int target) {
//右下角一定是最大的植物，从右下角的开始往左上角找，一旦target大于对角线上的某个值，则target就位于当前值的右侧或下侧
if (plants == null || plants.length == 0) {
return false;
}
int i = 0;
int j = plants[0].length – 1;
while (j >= 0 && i < plants.length) { if (plants[i][j] > target) {
j–;
} else if (plants[i][j] < target) { i++; } else { return true; } } return false; } }

0 赞同 0 条回复

登录以回复

mpweixin用户永久会员 2023年7月25日上午12:08

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

        int rowLen = matrix.length;
        int colLen = matrix[0].length;

        //从左下角开始查找
        int row = rowLen - 1;
        int col = 0;

        while(row >= 0 && col < colLen){
            if(matrix[row][col] > target){
                row--;
            }else if(matrix[row][col] < target){
                col++;
            }else{
                return true;
            }
        }

        return false;
    }
}

0 赞同 0 条回复

Vow the vow。普通 2023年7月24日下午8:41

时间复杂度O(logn)

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;
    }

0 赞同 0 条回复

张开怀普通 2023年7月24日下午8:27

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()){
            return false;
        }
        int cols = matrix.size()；
        int rows = matrix[0].size();
        // 左下角的位置
        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;
    }
};

时间复杂度：O(m+n)
空间复杂度：O(1)

0 赞同 0 条回复

yxy 普通 2023年7月24日下午6:30

时间复杂度O(logmn)

class Solution {
public:
    //最终版
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) 
    {
        if(matrix.empty()||matrix[0].empty())
            return false;
        int n=matrix.size();
        int m=matrix[0].size();
        int i=0,j=m-1;
        while(i<n&&j>=0)
        {
            if(matrix[i][j]==target)
                return true;
            else if(matrix[i][j]<target)
                i++;
            else
                j--;
        }
        return false;
    }
};

0 赞同 0 条回复

花老爷普通 2023年7月23日下午6:04

暴力
时间：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][j] == target)
                    return true;
            }
        }
        return false;
    }
}

Z形查找
时间：O(m+n)
空间：O(1)

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

0 赞同 0 条回复

Yodl. 普通 2023年7月23日下午4:13

//时间复杂度O(m+n),空间复杂度O(1)
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int i = matrix.size() - 1, j = 0;
        while(i >= 0 && j < matrix[0].size())
        {
            if(matrix[i][j] > target) i--;
            else if(matrix[i][j] < target) j++;
            else return true;
        }
        return false;
    }
};

0 赞同 0 条回复

Ming 普通 2023年7月23日下午4:08

思路在代码中

  public boolean findNumberIn2DArray(int[][] matrix, int target) {
          if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0){
            return false;
        }
        // 视角移到左下角，上面的数比他小，右边的数比他大
        int n = matrix.length;
        int m = matrix[0].length;

        int row =  n - 1;
        int col = 0;
        while(row >= 0 && col < m) {
            if(target > matrix[row][col]) {
                col++;
            } else if(target < matrix[row][col]) {
                row--;
            } else {
                return true;
            }
        }
        return false;
    }

0 赞同 0 条回复

怀瑾永久会员 2023年7月23日下午4:00

“`C++
bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target){
if(matrix==NULL||matrixSize==0||matrixColSize[0]==0)
{
return 0;
}
int i = 0;
int j = matrixColSize[0]-1;
while(i=0)
{
if(matrix[i][j]==target)
{
return 1;
}
if(matrix[i][j]>target)
{
j–;
continue;//不加continue可能会出现两次判断都进行，且也可能在第二次判断出现越界情况
}
if(matrix[i][j]

0 赞同 0 条回复

登录以回复

# 回答此问题取消回复

后才能回答

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

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复