[每日一道小算法（二十一）][二维数组] 二维数组中查找某个值

淩亂°似流年 2023-07-04 14:17 47阅读 0赞

前言：  
日常打卡。

#### 题目描述 ####

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

#### 题目解析 ####

看到这道题，我们能立马想出解决方案。最简单的就是我们遍历一遍数组呗，然后一个个进行比对就好啦。既然这道题这么出了，并且是一个二维数组，肯定是不想让我用这么简单的方法来解决这道题，肯定有他的用意。并且如果直接使用遍历的方法，时间复杂度太高了O（n2）。所以这个方法不好，我们再来看看其他解决方法。  
首先我们来看这个二维数组的特性，我们把二维数组看作是一个矩阵，每一行每一列都一个从小到大递增，根据这个特性，我们可以看出，我们把这个矩阵右上角当作第一个值，如果这个值等于查找值，那么直接找到，如果这个值大于查找值，根据特性，这一列都不会符合，如果这个值小于查找值，那么这一行都不会符合，通过这种方式逐渐缩小矩阵，直到最后找到查找值或者没找到。这个方法的时间复杂度为O（行高+列宽）。这个时间复杂度要优于直接遍历的时间复杂度的。下面来看代码样例。

### 代码样例 ###

public static boolean Find(int target, int [][] array) { 
            if(array.length<1||target<0||array==null)
            { 
                return false;
            }
            int rows=array.length; //得到行长度
            int cols=array[0].length; //列长度
            int col = cols - 1;  //开始列号
            int row = 0; //开始行号
            while(col>=0 && col<cols && row<rows && row>=0)
            { 
                if(array[row][col] == target)
                { 
                    return true;
                }
                else if(array[row][col] > target)
                { 
                    col--;
                }else { 
                    row++;
                }
            }
            return false;
        }