二维数组中的查找(中等难度)-阿里云开发者社区

二维数组中的查找(中等难度)

2022-12-18 75

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 二维数组中的查找(中等难度)

题目概述(中等难度)

题目链接：

二维数组中的查找

思路与代码

思路展现

方法1 暴力法

如果不考虑二维数组排好序的特点，则直接遍历整个二维数组的每一个元素，判断目标值是否在二维数组中存在。

依次遍历二维数组的每一行和每一列。如果找到一个元素等于目标值，则返回 true。如果遍历完毕仍未找到等于目标值的元素，则返回 false。

代码示例

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

时间复杂度：O(nm)二维数组中的每个元素都被遍历，因此时间复杂度为二维数组的大小。

空间复杂度：O(1)

方法2 标志数

这块建议大家直接看k神的解答，我直接把解答放在了下面:

K神解答

代码示例

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
       int i = matrix.length-1;
       int 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;
       } 
}