剑指 Offer 04. 二维数组中的查找

妖狐艹你老母 2024-03-23 17:15 7阅读 0赞

#### 目录 ####

*   *  方法一
     *  方法二

题目来源  
[剑指 Offer 04. 二维数组中的查找][Offer 04.]

### 方法一 ###

暴力法

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

![在这里插入图片描述][7fc21e1b93874898895f7374d17f58ea.png]

### 方法二 ###

![在这里插入图片描述][8c51d27dc37b44edb940ba8b59cdce56.png]

从矩阵 matrix 左下角元素（索引设为 (i, j) ）开始遍历，并与目标值对比：  
当 matrix\[i\]\[j\] > target 时，执行 i-- ，即消去第 i 行元素；  
当 matrix\[i\]\[j\] < target 时，执行 j++ ，即消去第 j 列元素；  
当 matrix\[i\]\[j\] = target 时，返回 true ，代表找到目标值。  
若行索引或列索引越界，则代表矩阵中无目标值，返回 false 。

时间复杂度 O(M+N)：其中，N和 M分别为矩阵行数和列数，此算法最多循环 M+N 次。

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

![在这里插入图片描述][1037ba7f6aba49ba97c1136b7ff47999.png]

[Offer 04.]: https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
[7fc21e1b93874898895f7374d17f58ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/ee446455badd45208d042deb55064a6b.png
[8c51d27dc37b44edb940ba8b59cdce56.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6abb283606384d00bb5626c9b48b0ae8.png
[1037ba7f6aba49ba97c1136b7ff47999.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/17868412f7d5435ca6eeafbfe9a6fce7.png