【C语言】每日一题（杨氏矩阵查找数）

杨氏矩阵介绍：

既然在杨氏矩阵中查找数，那什么是杨氏矩阵呢？

矩阵的每行从左到右是递增的，矩阵从上到下是递增的。

例如：

方法：

看到这题我们马上就可以想到遍历一遍数组，但无疑这是效率最低的算法，就不展开详细来讲了

那还有什么样的算法呢？

我们发现这歌矩阵是特殊的：左到右是递增的，矩阵从上到下是递增的
可以利用这个规律来做题

思路：

我们发现右上角的数比较特殊，是一行中最大的，一列中最小的，
可以用右上角的数字与target，也就是我们要找的目标数比较
设arr[x][y]为右上角元素

有三种情况：

1.当 arr[x][y]==target，我们返回

2.当 arr[x][y]>target，说明target有可能在这列
则我们需要令 y--，向左进行缩减排查

3.当 arr[x][y]<target，说明target不可能在这一行，
需要 x++，到下一行继续寻找

代码实现：

//我们假设找到了返回1，没找到返回1
int find(int arr[][3], int row, int col,int target)
{int x = 0;int y = col - 1;while (x <= row && y >= 0){if (arr[x][y] == target)return 1;else if (arr[x][y] < target)x++;elsey--;}return 0;//没找到时返回0
}
int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int target = 0;scanf("%d", &target);int ret = find(arr, 3, 3, target);if (ret == 1)printf("找到了\n");elseprintf("没找到\n");return 0;
}

那如果我们要实现返回下标的又该如何写呢？
在C语言中是不存在同时返回2个参数的方法的
不过
我们可以将两个数的地址传参，用解引用进行对原数的修改

代码实现：

void find(int arr[][3], int* row, int* col, int target)
{int x = 0;int y = 2;while (x <= row && y >= 0){if (arr[x][y] == target){*row = x;*col = y;return;}else if (arr[x][y] < target)x++;elsey--;}*row = -1;*col = -1;
}
int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int target = 0;scanf("%d", &target);int x = 3;int y = 3;find(arr, &x, &y, target);if (x != -1)printf("找到了，下标是%d %d\n", x, y);elseprintf("没找到\n");return 0;
}

欢迎大家纠错与讨论