本篇内容主要讲解“C语言如何实现杨氏矩阵”,感兴趣的免费云主机域名朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“C语言如何实现杨氏矩阵”吧!题目如下:有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在。要求:时间复杂度小于O(N);题干中所描述的矩阵被称作杨氏矩阵,然后让你在这个这个矩阵中查找一个数字。其实在矩阵中查找一个数字并不难,只需采取遍历的方式,将矩阵中每个元素拿出来比较即可。但这道题还有一个要求就是时间复杂度必须小于O(N),也就是说不能采用遍历的方式来查找。因此我们需要根据杨氏矩阵的特点来写一个新的算法进行查找。如下图所示,为一个3×3的杨氏矩阵。根据题目我们总结一下杨氏矩阵的两个特点:1. 同一行的元素由左向右依次递增2. 同一列的元素从上到下依次递增通过这两点我们会发现这个矩阵有两个元素是特殊元素。右上角元素3为其所在行最大的元素,为其所在列最小的元素左下角元素7为其所在行最小的元素,为其所在列最大的元素因此我们可以采用以下方法:先拿出右上角的元素3来和所查找的元素比较,如果3比要查找的元素大,那说明该元素绝不可能在第一行,因此我们就可以直接排除一行的元素。如果3比要查找的元素小,那说明该元素绝不可能在最后一列,因此我们就可以直接排除一列的元素现在假设我们排除了一行的元素,那接下来的矩阵就变成了这样:这时6又变成了右上角的元素,然后重复上一步的操作,假设我们这次排除了一列的元素,那接下来的矩阵就变成了这样:于是5变成了右上角的元素,继续重复上一步操作,这样每一次查找我们都可以排除一行或者一列的元素,大大的提高了算法效率。当然上述举例我是以右上角元素为基准的,如果以左下角元素为基准也可以得到相同的结果,大家不妨自己来试一下。实现代码如下:这里我们将查找杨氏矩阵元素的过程封装在一个函数中。函数接收4个参数,分别是二维数组的地址,行数,列数和要查找的元素。通过返回值来判断是否找到。在函数内部定义一个坐标(x, y)表示右上角元素,当x等于行数是说明已经越界(数组下标是从0开始的),那要查找的元素必然不存在。当列数小于0也一样。当排除一行的时候,给x的值加1即可;排除一列的时候,给y的值减1即可。运行结果:到此,相信大家对“C语言如何实现杨氏矩阵”有了更深的了解,不妨来实际操作一番吧!这里是百云主机网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
本篇内容介绍了“Python如何解析URL参数”的有关知识,在实际案例的操作过程中,不少人都会免费云主机域名遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!在日常工作的项目中,经常需要将一个传递过来的URL进行…
免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。