详解扬氏矩阵

详解扬氏矩阵

🧿 杨氏矩阵 ：这个数字矩阵的每行从左到右是递增的，每列从上到下是递增的。杨氏矩阵。是对组合表示理论和舒伯特演算很有用的工具。它提供了一种方便的方式来描述对称和一般线性群的群表示，并研究它们的性质。杨氏矩阵是剑桥大学大学数学家阿尔弗雷德·扬在1900年提出。然后在1903年，它被用于格奥尔格·弗罗贝纽斯的对称群研究中。它的理论得益于许多数学家的贡献得到进一步发展，包括珀西·麦克马洪，W.V.D.霍奇，G.deB.罗宾逊，吉安·卡咯罗塔，阿兰拉斯克斯，马塞尔·保罗斯库森博格和理查德·P·史丹利。

/***********************************************************************
目的：请编写程序在这样的矩阵中查找某个数字是否存在，要求时间复杂度小于O(N)
分析：注意并没有规定它得等差递增，所以不要钻牛角尖
1 2 3 | 1 2 3
2 3 4 | 4 5 6
3 4 5 | 7 8 9
以上两个即是杨氏矩阵
平台：Visual studio 2017 && windows
*************************************************************************/
📝 实现代码1

#include<stdio.h>
int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };//查找数字7int i = 0;int j = 0;for(i = 0; i < 3; i++){for(j = 0; j < 3; j++){if(7 == arr[i][j]){printf("找到了，下标是%d，%dn", i, j);}}}if (3 == i){printf("找不到n");}return 0;
}

💨 这样虽然能解决问题，但却不满足要求，因为上面这个代码的时间复杂度为O(N)

/***********************************************************************
目的：改进代码1
分析：通过右上角的元素来查找(它是一行里最大的&&一列里最小的)

步骤：
▶ 找到3，因为3 < 7，且3是一行里最大的，所以排除一行
▶ 找到6，因为6 < 7，且6是一行里最大的，所以排除一行
▶ 找到9，因为9 > 7，所以7有可能在这一行里；因为9是这一行里最小的，所以排除一列
▶ 找到8，因为8 > 7，且8是一列里最小的，所以排除一列
▶ 找到7，因为7 == 7，所以找到了

❓❔ 当然只能局限于右上角吗
我们发现对于杨氏矩阵中要查找某一个数字是否存在，且它的时间复杂度要小于O(N)时：
▶ 左上角是一行、一列中最小的；右下角是一行、一列中最大的，所以不能利用查找
▶ 右上角是一行中最大的，一列中最小的；左下角是一行中最小的，一列中最大的，所以能利用查找

平台：Visual studio 2017 && windows
*************************************************************************/
📝 改进代码1

#include<stdio.h>
int FindNum1(int arr[][3], int r, int c, int k)
{//这里是利用右上角来查找int x = 0;int y = c - 1;while(x < 3 && y >= 0){if(arr[x][y] < k){//排除行x++;}else if(arr[x][y] > k){//排除列y--;}else{//找到了printf("%d, %dn", x, y);return 1;}}//找不到return 0;
}
int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int k = 7;//如果找到了就返回1,否则返回0int ret = FindNum1(arr, 3, 3, k);if(1 == ret){printf("找到了n");}else{printf("找不到n");}return 0;
}

💨 这个代码虽然满足了要求，但有一点不好的地方是我们希望找到后打印出坐标来，同时也不希望它FindNum1函数中实现。

/***********************************************************************
目的：改进代码2使得FindNum1代码功能独立性更好
分析：在传参的时候传定义好的横纵坐标的地址 ，然后再FindNum2中找到k后，把横纵坐标的值交给指针即可
平台：Visual studio 2017 && windows
*************************************************************************/
📝 改进代码2

#include<stdio.h>
int FindNum2(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{//这里找到了k，此时再将k的坐标赋值带回去*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 = 7;int x = 3;//行int y = 3;//列//这里的&x，&y的作用是//1.传入参数//2.带回值//这种参数的设计叫做返回型参数	int ret = FindNum2(arr, &x, &y, k);//改进处if(1 == ret){printf("找到了n");printf("%d, %dn", x, y);}else{printf("找不到n");}return 0;
}