首页 > 其他分享 >杨氏矩阵

杨氏矩阵

时间:2023-01-14 16:31:09浏览次数:41  
标签:右上角 元素 矩阵 查找 杨氏 一列

问题:有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在。 要求:时间复杂度小于O(N);

杨氏矩阵普及:杨氏矩阵是对组合表示理论和舒伯特演算很有用的工具。它提供了一种很方便的方式来描述对称和一般线性群表示,并研究它们的性质。

分析:对于杨氏矩阵老说,右上角和左下角的元素是有特点的。右上角的元素是一行中最大的,一列中最小的。左下角的元素是一行中最小的,是一列中最大的。所以我们可以从右上角或者左下角开始查找。比如(线性搜索方法):从右上角开始查找的时候,右上角的元素比我们要查找元素小,我们就可以去掉右上角元素所在的这一行;右上角的元素比我们要查找的元素大,我们就可以去掉右上角元素所在的这一列。然后依然找右上角的元素继续和要查找的元素与比较。这样每一次比较去掉一行或者去掉一列。这个查找效率是高于遍历数组元素的,所以时间复杂度是小于O(N),也满足题目要求。

代码:

杨氏矩阵_遍历数组

代码:

杨氏矩阵_遍历数组_02

标签:右上角,元素,矩阵,查找,杨氏,一列
From: https://blog.51cto.com/u_15830263/6007627

相关文章

  • hdu:Problem Description Lele now is thinking about a s(矩阵快速幂)
    ProblemDescriptionLelenowisthinkingaboutasimplefunctionf(x).Ifx<10f(x)=x.Ifx>=10f(x)=a0 f(x-1)+a1 f(x-2)+a2 f(x-3)+……+a9 ......
  • 代码随想录算法训练营第二天|977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II
    一、参考资料有序数组的平方题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/文章讲解:https://programmercarl.com/0977.有序数组的平方.html视频讲......
  • 【Pytorch】多维矩阵的加法
    目录​​简介​​​​问题描述​​​​测试​​​​解释​​​​结语​​简介Hello!非常感谢您阅读海轰的文章,倘若文中有错误的地方,欢迎您指出~ ଘ(੭ˊᵕˋ)੭昵称:海轰......
  • 【Pytorch】将矩阵中的元素按照区间重新赋值
    目录​​简介​​​​场景描述​​​​解决方法​​​​结语​​简介Hello!非常感谢您阅读海轰的文章,倘若文中有错误的地方,欢迎您指出~ ଘ(੭ˊᵕˋ)੭昵称:海轰标签:程序......
  • 【Pytorch】计算矩阵中向量之间的两两相似性
    目录​​简介​​​​场景描述​​​​解决方法​​​​结语​​简介Hello!非常感谢您阅读海轰的文章,倘若文中有错误的地方,欢迎您指出~ ଘ(੭ˊᵕˋ)੭昵称:海轰标签:程序......
  • P1005 [NOIP2007 提高组] 矩阵取数游戏
    题目传送门前言今天依旧是不写高精的一天呢!(是的,这位作者又只拿了开\(LL\)的\(\color{yellow}{60}\)分)思路描述看到数据\(n,m\le80(30)\)就知道数组可以任性开,......
  • 74. 搜索二维矩阵
    问题链接https://leetcode.cn/problems/search-a-2d-matrix/description/解题思路我们可以确定,数据是有序的。所以我们有2种办法用二分来解决。第一种,我们可以写个下标......
  • LeetCode 54_螺旋矩阵
    LeetCode54:螺旋矩阵题目给你一个m行n列的矩阵matrix,请按照顺时针螺旋顺序,返回矩阵中的所有元素。示例1:输入:matrix=[[1,2,3],[4,5,6],[7,8,9]]输出:[1,2,3......
  • 【算法原理】矩阵乘法
    【算法原理】矩阵乘法一般是矩阵乘法+快速幂,结合\(dp\)普通矩阵乘法:矩阵乘法有结合律,无交换律。因此在计算一长串矩阵相乘的时候,可以依据计算难度选择计算顺序,从而......
  • 【LeetCode数组#5行为模拟】螺旋矩阵II
    螺旋矩阵II力扣题目链接(opensnewwindow)给定一个正整数n,生成一个包含1到n^2所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。示例:输入:3输出:[[1,......