从杨氏矩阵找数

￡神魔★判官ぃ 2023-09-27 12:44 142阅读 0赞

杨氏矩阵，是对组合表示理论和舒伯特演算很有用的工具。它提供了一种方便的方式来描述对称和一般线性群的群表示，并研究它们的性质。有一个二维数组的每行从左到右是递增的，每列从上到下是递增的. 在这样的数组中查找一个数字是否存在。 时间复杂度小于O(N)。

这里要求 时间复杂度小于O(N)，所以就不能用双重循环去寻找这个数，我们可以根据它的特点（行从左到右是递增的，每列从上到下是递增的）下手，如图

![c1650d26a93c44d98e63d6c5b52b067f.jpeg][]

我们可以选择右上角的数去和我们要找的数进行比较，如果右上角的数大于我们要找的数，我们就可以去除右上角的数所在的列，因为右上角的数是该列最小的数，所以排出这一列，要是右上角的数小于我们要找的数，我们就可以去除右上角的数所在的行，因为右上角的数是该行最大的数，所以排出这一行，然后就可以设置一个循环，再次用新的右上角的数与我们要找的数进行比较，直到我们右上角的数等于我们要找的数。我们了解了大概后，我们就可以写代码了，

#include<stdio.h>
    int Find_num(int arr[][3],int*px,int*py,int k)
    {
        int x=0;
        int y=*py-1;
        while(x<*px&&y>=0)
        {
            if(arr[x][y]<k)
            {
                x++;
            }
            else if (arr[x][y]>k)
            {
                y--;
            }
            else
            {
                *px=x;
                *py=y;
                return 1;
            }
        }
        return 0;
    }
    int main()
    {
        int arr[3][3]={1,2,3,4,5,6,7,8,9};
        int k=9;
        int x=3;//行
        int y=3;//列
        int ret=Find_num(arr,&x,&y,k);//传x,y的地址是为了，找到我们想要找的数之后，打印他的坐标
        if(ret==1)
        {
            printf("找到了\n");
            printf("坐标为:(%d,%d)\n",x,y);
        }
        if(ret==0)
        {
            printf("没有找到\n");
        }
        return 0;
    }

代码里备注一些注释帮助大家的理解，大家下去多多练习吧，谢谢大家的支持。

[c1650d26a93c44d98e63d6c5b52b067f.jpeg]: https://img-blog.csdnimg.cn/c1650d26a93c44d98e63d6c5b52b067f.jpeg