《剑指offer》--004--二维数组中的查找（杨氏矩阵）

浅浅的花香味﹌ 2022-06-01 03:12 176阅读 0赞

[《剑指offer》–目录索引][offer]

**题目：**

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

**思路：**

> ①因为从左到右递增，从上到下递增，则**每行的最后一列的元素**是其所属行中最大的，又是其所属列中最小的，我们**以二维数组中右上角元素为起点**，暂且称它为顶角元素；  
> ②当查找元素大于顶角元素时，查找元素一定在顶角元素的下边行中；当查找元素小于顶角元素是，查找元素一定在顶角元素的左边列中；

**图解：**

> 以数组a\[3\]\[4\]=\{ \{1,3,5,7\},\{2,4,6,8\},\{3,7,11,15\}\};为例
> 
> 1>查找4  
> ![这里写图片描述][SouthEast]  
> 2>查找11  
> ![这里写图片描述][SouthEast 1]  
> 3>查找14  
> ![这里写图片描述][SouthEast 2]

**代码如下：**

int YangArray1(int arr[][4],int number)//二维数组，从右上角开始
    {
        if(arr == NULL)//传参异常
        {
            return -1;  
        }
        int i=0,j=3;
        while(i < 3 && j >= 0)
        {
            if(arr[i][j] > number)
            {
                j--;
            }
            else if(arr[i][j] < number)
            {
                i++;
            }
            else
            {
                return 1;//找到，返回1
            }
        }
        return 0;//没找到，返回0
    }

**进阶：**

int YangArray2(int* arr,int number,int rows,int cols)//一维数组
    {
        if(arr == NULL || rows <= 0 || cols <= 0)//传参异常
        {
            return -1;  
        }
        int row=0;
        int col=cols-1;
        while(row < rows && col >= 0)
        {
            if(arr[row*cols+col] > number)
            {
                col--;
            }
            else if(arr[row*cols+col]  < number)
            {
                row++;
            }
            else
            {
                return 1;//找到，返回1
            }
        }
        return 0;//没找到，返回0
    }

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

**两种方法的优缺点比较：**

> 用二维数组的代码优点是简单易懂；缺点是局限性比较大，只能传固定行数和列数的数组，当数组的行列改动时，代码也要改动；  
> 用一维数组的代码优点是①比较灵活②二维数组就是一维数组，这样写可以体现自己对二维数组的理解；缺点是一开始不容易看懂，希望上图能帮助读者理解。

**测试代码：**

void test1()//测试代码1，正常情况
    {
        int a[][4]={
       1,3,5,7,2,4,6,8,3,7,11,15};
    
        printf("%d\n",YangArray1(a,1));//最小值情况
        printf("%d\n",YangArray1(a,15));//最大值情况
        printf("%d\n",YangArray1(a,0));//不存在情况
        printf("%d\n",YangArray1(a,-1));//比最小值还小情况
        printf("%d\n",YangArray1(a,16));//比最大值还大情况
    
        printf("%d\n",YangArray2((int *)a,1,3,4));//最小值情况
        printf("%d\n",YangArray2((int *)a,15,3,4));//最大值情况
        printf("%d\n",YangArray2((int *)a,0,3,4));//不存在情况
        printf("%d\n",YangArray2((int *)a,-1,3,4));//比最小值还小情况
        printf("%d\n",YangArray2((int *)a,16,3,4));//比最大值还大情况
    }
    
    void test2()//测试用例2，异常情况
    {   
        int a[][4]={
       1,3,5,7,2,4,6,8,3,7,11,15};
    
        printf("%d\n",YangArray1(NULL,1));//空指针情况
        printf("%d\n",YangArray2(NULL,1,3,4));//空指针情况
        printf("%d\n",YangArray2((int *)a,1,0,4));//行传参异常情况
        printf("%d\n",YangArray2((int *)a,1,3,0));//列传参异常情况
    }
    
    int main()
    {   
        test1();
        test2();
        return 0;
    }

**运行结果：**  
![这里写图片描述][SouthEast 4]

[offer]: http://blog.csdn.net/w_y_x_y/article/details/79209805
[SouthEast]: /images/20220601/2aace24196e743edb29dd8a06102336b.png
[SouthEast 1]: /images/20220601/bd1d44b70472488fb990c585445343c9.png
[SouthEast 2]: /images/20220601/0d00fa9050564a22bb7542756b54d704.png
[SouthEast 3]: /images/20220601/16ac574aab6f40c49b7aa1dfc76a873c.png
[SouthEast 4]: /images/20220601/7b67cc21ae0641c6a3a708bc64eccf49.png