🧿 杨氏矩阵 ：这个数字矩阵的每行从左到右是递增的，每列从上到下是递增的。杨氏矩阵。是对组合表示理论和舒伯特演算很有用的工具。它提供了一种方便的方式来描述对称和一般线性群的群表示，并研究它们的性质。杨氏矩阵是剑桥大学大学数学家阿尔弗雷德·扬在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 }; //查找数字7 int i = 0; int j = 0; for(i = 0; i < 3; i++) { for(j = 0; j < 3; j++) { if(7 == arr[i][j]) { printf("找到了，下标是%d，%d\n", 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, %d\n", 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,否则返回0 int 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, %d\n", x, y); } else { printf("找不到\n"); } return 0; }
