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

这篇具有很好参考价值的文章主要介绍了【C语言】每日一题(杨氏矩阵查找数)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

杨氏矩阵介绍:

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

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

例如:
【C语言】每日一题(杨氏矩阵查找数),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++;
		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个参数的方法的
不过
我们可以将两个数的地址传参,用解引用进行对原数的修改

代码实现:

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C语言】杨氏矩阵中寻找元素

    杨氏矩阵 有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从下到上递增的(杨氏矩阵的定义),请编写程序在这样的矩阵中查找某个数字是否存在。 形如这样的矩阵就是杨氏矩阵(本质上是一个二维数组) 时间复杂度小于O(N) 因为题目要求时间复杂度小于O(N),所以

    2024年02月14日
    浏览(36)
  • C语言——oj刷题——杨氏矩阵

    目录 1. 理解杨氏矩形的特点 2. 实现杨氏矩形查找算法 3. 编写示例代码 当我们谈到杨氏矩形时,我们指的是一种在二维数组中查找目标元素的高效算法。它是由杨氏(Yan Shi)教授提出的,因此得名为杨氏矩形。 杨氏矩形问题的场景是这样的:给定一个有序的二维数组,每一

    2024年02月20日
    浏览(39)
  • C语言题目:在杨氏矩阵中,寻找某个数字是否存在

    C语言题目:杨氏矩阵         这种矩阵,只需要一个二维数组就可以创建,查找时也只需要在二维数组里查找就可以了。         但是,如果这样查找,尝试过的人都知道,这样就需要使用两个循环,此时的时间复杂度就是0(n²)了。 可是题目要求时间复杂度,为

    2023年04月08日
    浏览(33)
  • 每日一题 — 二分查找

    704. 二分查找 - 力扣(LeetCode)   朴素二分查找模板:  代码:

    2024年04月23日
    浏览(32)
  • 每日一题(LeetCode)----二分查找(一)

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 104 -104 = nums[i] = 104 nums 为 无重复元素 的 升序 排列数

    2024年02月08日
    浏览(49)
  • 头歌(C语言)-数据结构与算法-查找-第1关:实现折半查找

    任务描述 相关知识 编程要求 测试说明 任务描述 本关要求通过补全函数 BSL_FindKey 来实现在已排序的顺序表中查找关键码值为 key 的结点并返回该结点的编号。 相关知识 折半查找通常是针对顺序存储的线性表,线性表的结点按关键码从小到大排序,后面称之为折半查找的顺序

    2024年02月10日
    浏览(60)
  • C语言的三个经典题目:三步翻转法、杨氏矩阵、辗转相除法

    三步翻转法是C语言中用来求旋转字符串的一种进阶方法,我们以具体例题对其进行介绍。 例:求一个字符串左旋n个字符后得到的新字符串 普通方法实现 我们知道,左旋一个字符一共分为三步: 将字符串的第一个字符存放到临时变量中; 将字符串中除’\\0’外的所有字符整

    2024年02月02日
    浏览(48)
  • 二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”

    各位CSDN的uu们你们好呀,今天小雅兰的内容仍然是二叉树和Leetcode每日一题,下面,就让我们进入二叉树的世界吧!!! 这个题目需要重新定义一个函数,函数参数需要有左子树和右子树,题目所给定的函数无法解决问题。 每个不为空的结点,都可以认为是一棵子树的根 

    2024年02月16日
    浏览(43)
  • 二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    各位CSDN的uu们你们好呀,今天继续数据结构与算法专栏中的二叉树,下面,让我们进入二叉树的世界吧!!! 二叉树(上)——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客 二叉树链式结构的实现 二叉树链式结构的实现 求二叉树的高度 但是这种写法有很大的问题

    2024年02月17日
    浏览(38)
  • (哈希表) 1002. 查找共用字符 ——【Leetcode每日一题】

    难度:简单 给你一个字符串数组 words ,请你找出所有在 words 的每个字符串中都出现的共用字符( 包括重复字符 ),并以数组形式返回。你可以按 任意顺序 返回答案。 示例 1: 输入:words = [“bella”,“label”,“roller”] 输出:[“e”,“l”,“l”] 示例 2: 输入:words = [“

    2024年02月08日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包