C语言——实现杨氏矩阵

什么是杨氏矩阵？

概念：

有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的

eg：

1 2 3
4 5 6 
7 8 9

题目：

请编写程序在这样的矩阵中查找某个数字是否存在。

要求：时间复杂度小于O(N);

分析：

我们仔细分析，不难发现，对于杨氏矩阵来说，

右上角和左下角的元素是有特点的。

右上角的元素是一行中最大的，一列中最小的。

左下角的元素是一行中最小的，是一列中最大的。

所以我们可以从右上角或者左下角开始查找。

比如：

从右上角开始查找的时候，右上角的元素比我们要查找元素小，我们就可以去掉右上角元素所在的这一行；

右上角的元素比我们要查找的元素大，我们就可以去掉右上角元素所在的这一列。

然后依然找右上角的元素继续和要查找的元素与比较。

这样每一次比较去掉一行或者去掉一列。

这个查找效率是高于遍历数组元素的，所以时间复杂度是小于O(N)，也满足题目要求。 

find_k(int arr[3][3], int r, int c,int k)
{int x = 0;int y = c - 1;while (1){if (arr[x][y] < k){arr[x][y] = arr[x++][y];//x++;}else if (arr[x][y] > k){arr[x][y] = arr[x][y--];//y--;}else{printf("找到了，位置为%d,%d", x, y);break;}}
}
int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int k = 7;find_k(arr, 3, 3,k);return 0;
}

优化：传地址过去，可以直接返回到主函数判断

int find_k(int arr[3][3], int *px, int *py, int k)
{int x = 0;int y = *py-1;int flag = 0;while (x <= *px - 1 && y>=0){if (arr[x][y] < k){x++;}else if (arr[x][y] > k){y--;}else{*px = x;*py = y;flag = 1;return 1;}}if (flag == 0)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;int ret =find_k(arr,&x,&y,k);if (ret == 0)printf("找不到了");if(ret ==1)printf("下标为%d,%d", x,y);return 0;
}