OJ刷题：杨氏矩阵【建议收藏】

看见这个题目，很多人的第一反应是遍历整个数组查找数字，但是这种方法不仅效率低，而且远远不能满足题目要求。下面介绍一种高效的查找方法：

代码实现：

#include <stdio.h>int Yang_Find_Num(int arr[][3], int r, int c,int k)
{int x = 0;int y = c - 1;while (x <= r - 1 && y >= 0){if (arr[x][y] < k){x++;}else if(arr[x][y] > k){ y--;}else{return 1;}}return 0;}int main()
{int arr[3][3] = { {1,2,3},{4,5,6},{7,8,9} };int k = 5;int ret = Yang_Find_Num(arr, 3, 3,k);if (ret == 1){printf("找到了\n");}else{printf("找不到\n");}return 0;
}

算法思想：

如果我们想返回查找数字的行，列下标，可以对上述代码进行改进：

#include <stdio.h>//返回型参数
int Yang_Find_Num(int arr[][3], int*px, int* py, int k)
{int x = 0;int y = *py - 1;while (x <= *px - 1 && 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 = 0;scanf("%d", &k);int r = 3;int c = 3;int ret = Yang_Find_Num(arr, &r, &c, k);//传址调用if (ret == 1){printf("下标为：%d %d\n",r,c);}else{printf("找不到\n");}return 0;
}

输出结果：