当前位置：
  1. 首页
  2. 剑指offer刷题第七期
  3. 问题详情

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

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

要求：

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

shuaidi
74 3

共以下 3 个回答

  • 陆狗陆狗 普通 2025年1月8日 上午9:30

    解题思路
    – 不能从(0,0)开始遍历，应该从左下角开始遍历。因为左下角满足一个性质，是同一列中的最大值，是同一列中的最小值
    【题解1】

    class Solution {
    public boolean findTargetIn2DPlants(int[][] plants, int target) {
        // 【错误】临界值
        if (plants.length == 0 || plants[0].length == 0) {
            return false;
        }
        // 从左下角开始遍历。因为左下角满足一个性质，是同一列中的最大值，是同一列中的最小值
        int i = plants.length - 1;
        int j = 0;
        // 【错误】循环条件写成了||，之前想的是可能会出现到了第0行，结果在第0行的右边，但是这种情况&&是能够涵盖的，反而||会导致越界
        while (i >= 0 &&  j <= plants[0].length - 1) {
            if (plants[i][j] == target) {
                return true;
            } else if (plants[i][j] < target) {
                // 小于。右移，因为右边的比较大
                j++;
            } else {
                // 大于。上游，因为上边的比较小
                i--;
            }
        }
        return false;

    }
}
    • 错误点1：临界值的判断
    • 错误点2：循环条件写成了||，之前想的是可能会出现到了第0行，结果在第0行的右边，但是这种情况&&是能够涵盖的，反而||会导致越界
    0 赞同 0 条回复
  • Aatorx 永久会员 2024年12月30日 下午3:20 
    class Solution {
public:
    bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {
        int i = plants.size() - 1;
        int j = 0;
        while(i >= 0 && j < plants[0].size()) {
            if(plants[i][j] == target) {
                return true;
            }else if(plants[i][j] > target) {
                i--;
            }else{
                j++;
            }
        }
        return false;
    }
};

    类似平衡二叉树查找。
    时间复杂度O(M+N)，空间复杂度O(1)。

    0 赞同 0 条回复
  • 晓宇 普通 2024年12月29日 下午3:09 
    class Solution {
public:
// 从右上往左下搜索
    bool findTargetIn2DPlants(vector>& plants, int target) {
        if(plants.empty() || plants[0].empty()) return false;
        int m = plants.size();
        int n = plants[0].size();

        for(int i = 0;i < m;i++){
            for(int j = n - 1;j >= 0; j--){
                if(plants[i][j] > target) continue;
                else if(plants[i][j] == target) return true;
                else break;
            }
        }
        return false;
    }
    // o(n+m) o(1)
};
    0 赞同 0 条回复

# 回答此问题

后才能回答