01 图解剑指Offer 二维数组中的查找 Java题解

偏执的太偏执、 2023-02-20 06:22 98阅读 0赞

### 01 图解剑指Offer 二维数组中的查找 Java题解 ###

*  01 图解剑指Offer 二维数组中的查找 Java题解
 *   *   *  题目链接
         *  题目描述
         *  题解:
         *  图解:
         *  代码:
         *  复杂度

# 01 图解剑指Offer 二维数组中的查找 Java题解 #

### [题目链接][Link 1] ###

### 题目描述 ###

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

### 题解: ###

如题从左到右依次递增，从上到下依次递增。那么取二维数组右上角的元素作为比较元素和target比较，如果target > 比较元素 就将比较元素向下挪一行即row++,如果target<比较角元素就将比较元素向右挪一列，即col–。如果相等返回true，循环此操作直到行和列超出范围。如果在此期间没有找到target则返回false。

### 图解: ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]

### 代码: ###

public class Solution { 
        public boolean Find(int target, int [][] array) { 
       		//判空语句
            if(array.length == 0 || array == null) { 
                return false;
            }
            int row = 0;
            int col = array[0].length - 1;
            while(col >= 0 && row < array.length){ 
                if(target > array[row][col]){ 
                    row++;
                }else if(target < array[row][col]){ 
                    col--;
                }else { 
                    return true;
                }
            }
            return false;
        }
    }

### 复杂度 ###

空间复杂度O(1) 没有额外空间  
最坏时间复杂度:  
(1)目标元素大于二维数组中的全部元素或 目标元素在左下角。O(array.length)  
(2) 目标元素小于二维数组中的全部元素O(array\[0\].length)

[Link 1]: https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200623203441125.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size_16,color_FFFFFF,t_70