剑指offer 04.二维数组中的查找 我妹妹都看的懂的方法_guankunkunwd的博客

⭐欢迎来到剑指offer好题精选专栏，一起学习，一起进步⭐

题目信息：

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

要求：时间复杂度O(n),空间复杂度O(1)

难度：中等

示例二维数组如下： 需要找的数字： 9
int [][]array = {
{1,2,8,9},
{2,4,9,12},
{4,7,10,13},
{6,8,11,15}
};

返回TRUE

---

解题思路：

假设target是要找的数，因为该二维数组满足，从上到下，从左到右依次递增的规律。也就是说又靠右右靠下的数是越来越大的。从二维数组的 第一行最后一列开始(最右上角的那个数)和target比较，如果大了，将列减小一列，如果小了，将行增加一行。直到找到该数字。

⭐从下面这个图来一起试一遍把⭐

1、num=9,target=10。num小于target，将行增加一行。

2、num=12，target=10，num>target。将列缩减一行。

3、num=9,target=10,num<target将行增加一行。

4、num=10、target=10 找到了！

---

代码如下：

C语言版：

bool Find(int* matrix, int rows, int cols, int number){
bool find = false;
if (matrix != NULL && rows > 0 && cols > 0){
int row = 0;
int col = cols - 1;
while (row < rows && col >= 0){
//1：第一次尝试数组右上角那个数字和number是否匹配
if (matrix[row * cols + col] == number){
find = true;
break;
}
//2:  如果数组中的数字大于number，就说明number应该在这个数字的左边,自己那一列不包含要查找的数字
else if (matrix[row * cols + col] > number){
--col;
}
//3:  如果数组中的数组小于number,就说明number应该在它的下边，自己那一行不包含要查找的数字
 else{
 ++row
 }
 }
 }
 return find;
 }

JAVA版：

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

你学会了吗？