算法篇-杨氏矩阵
问题
现有一个数字矩阵，矩阵的每行从左到右是递增，矩阵每列从上到下是递增，请编写程序在这样的矩阵中查找某个数字是否存在。复杂度小于O（n）
百度百科
杨氏矩阵，是对组合表示理论和舒伯特演算很有用的工具。它提供了一种方便的方式来描述对称和一般线性群的群表示，并研究它们的性质。有一个二维数组. 数组的每行从左到右是递增的，每列从上到下是递增的. 在这样的数组中查找一个数字是否存在。 时间复杂度小于O(N);
杨氏矩阵是剑桥大学大学数学家阿尔弗雷德·扬在1900年提出。然后在1903年，它被用于格奥尔格·弗罗贝纽斯的对称群研究中。它的理论得益于许多数学家的贡献得到进一步发展，包括珀西·麦克马洪，W.V.D.霍奇，G.deB.罗宾逊，吉安·卡咯罗塔，阿兰拉斯克斯，马塞尔·保罗斯库森博格和理查德·P·史丹利。
算法
方法一 暴力法
不考虑时间复杂度的情况下，直接双层循环暴力破解。在此不做过多解释。
代码：
#include<stdio.h> int FindNum(int arr[3][3], int test, int* r, int* c);//查找函数声明 int main() { int arr[3][3] = { {1,2,3},{4,5,6},{7,8,9} }; int test = 0;//保存用户想要查找的值 int row = sizeof(arr) / sizeof(arr[0]);//行长度 int col = sizeof(arr[0]) / sizeof(arr[0][0]);//列长度 scanf("%d", &test); int ret = FindNum(arr, test, &row, &col); if (ret == 1) { printf("找到了！在数组第%d行，第%d列的位置！\n", row, col); } else { printf("找不到！"); } return 0; } //查找函数 int FindNum(int arr[3][3], int test, int* r, int* c) {//返回0 - 未找到 返回1 - 找到 for (int i = 0; i < *r; i++) { for (int j = 0; j < *c; j++) { if (arr[i][j] == test) { *r = i; *c = j; return 1; } } } return 0; }
方法二
思路：
首先构造一个杨氏矩阵
在上表中可以找到俩个特殊点，一个是右上角，另一个是左下角。让测试值与特殊点左比较
令测试变量为test，数组名为arr
右上角：如果test比3大，那么对应的那一行都比test小，因为那一行中3是最大的，即可以排除一整行。同理如果test比3小，那么对于的那一列都比test大，因为3是那一列中最小的。以此进行直到遍历完数组或者找到test的值为止。
同理，
左下角规律是：如果test比3大，那么对应的一列都比test小，排除对应一列，如果test比3小，那么对应的一行都比test大，排除对应一行。其他同上循环进行即可。
例如：test=5 c从右上角开始
第一次 比较 arr[2][0] < test ,排除第一行
第二次 比较arr[2][1] > test， 排除第三列
第三次 比较 arr[1][1] < test， 排除第二行
第四次比较 arr[1][2] == test 找到了！
然后我们保存或者返回该元素所在的位置。
代码：
#include<stdio.h> int FindNum(int arr[3][3], int test, int* r, int* c);//查找函数声明 int main() { int arr[3][3] = { {1,2,3},{4,5,6},{7,8,9} }; int test = 0;//保存用户想要查找的值 int row = sizeof(arr) / sizeof(arr[0]);//行长度 int col = sizeof(arr[0]) / sizeof(arr[0][0]);//列长度 printf("请输入需要查找的值："); scanf("%d", &test); int ret = FindNum(arr, test, &row, &col); if (ret == 1) { printf("找到了！在数组第%d行，第%d列的位置！\n", row, col); } else { printf("找不到！"); } return 0; } //查找函数 int FindNum(const int arr[3][3], int test, int* r, int* c)//从右上角开始 { int x = 0; int y = *c - 1; while (x < *r && y >= 0) { if (arr[x][y] > test) {//排除一列 y--; } else if (arr[x][y] < test) {//排除一行 x++; } else { //此处修改主函数的长和宽，用于保存找到该元素的地址 *r = x; *c = y;// return 1; } } return 0; }
同理我们可以写出左下角的查找函数
//查找函数 int FindNum(const int arr[3][3], int test, int* p, int* q)//从左下角开始 { int x = *p - 1; int y = 0; while (x >= 0 && y < *q) { if (arr[x][y] > test) {//排除一列 x--; } else if (arr[x][y] < test) {//排除一行 y++; } else { *p = x; *q = y; return 1; } } return 1; }
运行结果
查找到的情况
未找到的情况
杨氏矩阵 - 完
