剑指offer刷题（1）：二维数组中的查找

红太狼 2022-05-26 23:00 146阅读 0赞

# 剑指offer刷题（1）：二维数组中的查找 #

刷题平台：[牛客网][Link 1]

# 二维数组中的查找 #

## 考点： ##

数组

## 1、题目描述 ##

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

## 2、解题思路 ##

对于一个二维数组，每一行都按照从左到右递增的顺序，每一列都按照从上到下递增的顺序排列，那么我们要想实现在这个数组中查找一个数。我们可以有很多个思路：  
\- 1、从第一个数据向后或者最后一个数据向前挨个查找一遍，直至查到该数据或者查完所有数据为止。虽然这种方法可以实现，但是比较麻烦。  
\- 2、我们可以利用数组行列都是递增的这么一个关系，因此我们可以从数组的左下角或者右上角开始查找，让所需要查找的数组与左下角或者右上角的数据进行比较，这样我们就可以利用矩阵的特性来不断的缩小数据应该出现的范围，从而可以很快的找出数据，当然也可以很快的确定该数据是否存在与改数组中。

## 3、算法实现 ##

### C实现 ###

为了方便这里的矩阵我并没有手动输入，而是直接放在程序里面的。

#include "stdio.h"
    
    bool Find(int targe, int *array, int rows, int cols);
    
    bool Find(int targe, int *array, int rows, int cols)
    {
        int i = rows - 1, j = 0;
        while (i > 0 && j < cols)
        {
            if (targe < array[cols * i + j]/**((int *)array + cols * i + j)*/  /*array[i][j]*/)
            {
                i--;
            }
            else if (targe>array[cols * i + j] /**((int *)array + cols * i + j)*/  /*array[i][j]*/)
            {
                j++;
            }
            else
            {
                printf("找到了该数，位置为（%d,%d）\t第%d行,第%d列\n",i,j,i+1,j+1);
                return true;
            }
        }
        printf("该数组中没有该数。\n");
        return false;
    }
    
    int main()
    {
        //先定义一个二维数组
        int a[5][5] = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 }, { 21, 22, 23, 24, 25 } };
        int targe=0;
        int cols = sizeof(a[0]) / sizeof(a[0][0]);
        int rows = sizeof(a) / sizeof(a[0]);
        printf("二维数组为：\n");
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                printf("%d\t", a[i][j]);
            }
            printf("\n");
        }
        printf("\n矩阵的大小为：rows=%d\tcols=%d\n", rows, cols);
        printf("请输入需要查询的数字：\n");
        scanf_s("%d", &targe);
        printf("需要查询的数字为：%d\n",targe);
    
        Find(targe, *a, rows, cols);
    }

### C++实现 ###

class Solution {
    public:
        bool Find(int target, vector<vector<int> > array) {
            int rows=array.size();
            int cols=array[0].size();
            int i=rows-1,j=0;
            while(i>=0&&j<cols)
            {
                if(target<array[i][j])
                {
                    i--;
                }
                else if (target>array[i][j])
                {
                    j++;
                }
                else
                {
                    return true;
                }
            }
            return false;
        }
    };

### C语言实现结果 ###

![这里写图片描述][SouthEast]

[Link 1]: https://www.nowcoder.com/ta/coding-interviews
[SouthEast]: /images/20220527/9362531fa547418e8e55e1312dd07dc6.png