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

    目录

    杨氏矩阵介绍：

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

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

    例如：
    在这里插入图片描述

    方法：

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

    那还有什么样的算法呢？

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

    思路：

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

    有三种情况：
    1.当 arr[x][y]==target，我们返回
    2.当 arr[x][y]>target，说明target有可能在这列
    则我们需要令 y--，向左进行缩减排查
    3.当 arr[x][y]，说明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;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    那如果我们要实现返回下标的又该如何写呢？
    在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++;
		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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    欢迎大家纠错与讨论

  • 相关阅读:
    计算机网络初识
    Wirshark学习笔记
    多路转接与Reactor
    Python抓取我的CSDN粉丝数，白嫖GithubAction自动抓取
    从0到1搭建redis6.0.7续更~
    数据库开发综合案例——仓库管理系统设计
    微服务从代码到k8s部署应有尽有系列（十三、服务监控）
    跨境电商影响搜索排名的因素有哪些
    数字化转型的“支点”是什么？
    java毕业设计基于Bootstrap框架的读书网站设计与实现mybatis+源码+调试部署+系统+数据库+lw
  • 原文地址：https://blog.csdn.net/2301_78636079/article/details/132782259