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

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

要求：

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

shuaidi

更新于 3 年前 109 8

共以下 8 个回答

hi 普通 2024年1月2日上午10:33

从右上角开始找：等于target，返回true；> target，搜索范围去掉一行；< target，去掉一列

class Solution {
public:
    bool findTargetIn2DPlants(vector>& plants, int target) {
        if(plants.size() == 0 || plants[0].size() == 0) return 0;

        int n = plants.size(), m = plants[0].size();
        int i = 0, j = m -1;
        while(i < n && j >= 0){
            if(plants[i][j] == target) return true;
            else if(plants[i][j] > target) j--;
            else i++;
        }

        return false; //循环过后没有找到证明没有
    }
};

0 赞同 0 条回复

June 普通 2023年11月27日上午10:02

class Solution {
    public boolean findTargetIn2DPlants(int[][] plants, int target) {
        int n = plants.length;
        if(n == 0)
            return false;
        int m = plants[0].length;

        int row = n - 1,col = 0; // 从左下角开始
        while(row >= 0 && col < m)
        {
            if(target > plants[row][col])
                col++;
            else if(target < plants[row][col])
                row--;
            else
                return true;
        }
        return false;
    }
}

0 赞同 0 条回复

桎梏普通 2023年9月16日下午1:34

lass Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //从左下角元素flag开始寻找 
        //若 target > flag, 则表示目标值在右边 则flag上面的元素全部小于target 执行i++
        //若 target < flag, 则表示目标值在上面 则flag右边的元素全部大于target 执行j--
        //获取左下角元素
        int i = matrix.length - 1, j = 0;

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

0 赞同 0 条回复

Marshan 普通 2023年9月12日下午8:51

很巧妙，充分利用了每行每列递增的特性，主要思想是从左下角或者右上角出发，每次排除一行或一列。

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
      if(matrix.size() == 0 || matrix[0].size() == 0){
        return false;
      }
      int m = matrix.size();
      int n = matrix[0].size();
      int i = m - 1,j = 0;

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

0 赞同 0 条回复

Mby 普通 2023年8月22日下午2:31

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

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月12日下午3:29

8.10 周四
Day31：下面是代码

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

0 赞同 0 条回复

NullPointerException 普通 2023年8月11日下午3:34
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
//感觉对二维数组按行/列二分一次次找
if(matrix.length0||matrix[0].length0)
{
return false;
}
int n=matrix.length;
int m=matrix[0].length;
for(int i=0;i<n;i++)//按行二分查找
{
int left =0;
int right=m-1;
int mid=(left+right)/2;
while(left<=right)
{
if(matrix[i][mid]target)
{
return true;
}
if(matrix[i][mid]<target)
{
left=mid+1;
}
if(matrix[i][mid]>target)
{
right=mid-1;
}
mid=(left+right)/2;
}
}
```
    return false;
}
```
}
0 赞同 0 条回复

登录以回复

AD钙奶普通 2023年8月11日上午11:47

双指针，由于有序，可以一左一右，模拟判断

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {

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

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

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

共以下 8 个回答

# 回答此问题 取消回复

# 回答此问题取消回复