杨氏矩阵介绍:
既然在杨氏矩阵中查找数,那什么是杨氏矩阵呢?
矩阵的每行从
左到右是递增
的,矩阵从上到下是递增
的。
例如:
方法:
看到这题我们马上就可以想到
遍历一遍数组
,但无疑这是效率最低的算法,就不展开详细来讲了
那还有什么样的算法呢?
我们发现这歌矩阵是特殊的:
左到右是递增
的,矩阵从上到下是递增
的
可以利用这个规律来做题
思路:
我们发现右上角的数比较特殊,是一行中最大的,一列中最小的,
可以用右上角的数字与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++;
else
y--;
}
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");
else
printf("没找到\n");
return 0;
}
那如果我们要实现返回下标的又该如何写呢?
在C语言中是不存在同时返回2个参数的方法的
不过
我们可以将两个数的地址传参,用解引用进行对原数的修改
代码实现:文章来源:https://www.toymoban.com/news/detail-705877.html
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++;
else
y--;
}
*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);
else
printf("没找到\n");
return 0;
}
欢迎大家纠错与讨论文章来源地址https://www.toymoban.com/news/detail-705877.html
到了这里,关于【C语言】每日一题(杨氏矩阵查找数)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!