题：在一个m行n列二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
&&&&例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字6，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。
这种行和列分别递增的矩阵，叫“杨氏矩阵”，而在这个矩阵中的查找称为：杨氏矩阵查找。
1、分治法，分为四个矩形，配以二分查找，如果要找的数是6介于对角线上相邻的两个数4、10，可以排除掉左上和右下的两个矩形，而递归在左下和右上的两个矩形继续找，如下图所示：
2、定位法，时间复杂度O（m+n）。首先直接定位到最右上角的元素，再配以二分查找，比要找的数（6）大就往左走，比要找的数（6）小就往下走，直到找到要找的数字（6）为止，如下图所示：
//杨氏矩阵查找
//定位法(完整代码)
#include &stdafx.h&
#include &stdio.h&
#include &iostream&
#define ROW 4
#define COL 4
bool YoungMatrix(int a[][COL], int Value)
int i = 0, j = COL-1;
while (i & ROW && j &= 0)
if (a[i][j] & Value)//比要找的数大,就往左走
else if (a[i][j] & Value)//比要找的数小,就往右走
int main()
int array[ROW][COL] = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } };
int KeyValue = 10;
bool TF = YoungMatrix(array, KeyValue);
if (TF == true)
cout && &TRUE,该值存在！& &&
cout && &FALSE,该值不存在！& &&
//定位法（网上参考代码）
bool YoungMatrix(int a[][COL], int Value)
int i = 0, j = COL-1;
int var = a[i][j];
while (true)
if (var==Value)
else if (var & Value&& i&ROW-1)
var=a[i++][j];
else if(var & Value&& j&0)
var=a[i][--j];
本文已收录于以下专栏：
相关文章推荐
1.查找给定的一个数是否在杨氏矩阵中？
在一个m行n列二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中...
杨氏矩阵搜索算法
个人信息：就读于燕大本科软件工程专业 目前大三;
本人博客：百度搜索“cqs_2012”即可;
个人爱好：酷爱数据结构和算法，希望将来搞科研为人民作出自己的贡献;
博客内容：...
人生苦短，都说必须python，那么我分享下我是如何从小白成为Python资深开发者的吧。2014年我大学刚毕业..
先看一个来自算法导论习题里6-3与剑指offer的一道编程题（也被经常用作面试题，本人此前去搜狗二面时便遇到了）：
    在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上...
问题：已知一个2维矩阵，其中的元素每一行从左至右依次增加，每一列从上到下依次增加。即对于矩阵Table有Table[i][j] ≤Table[i][j + 1], Table[i][j] ≤ Tabl...
定位法，时间复杂度O（m+n）。首先直接定位到最右上角的元素，再配以二分查找，比要找的数（6）大就往左走，比要找数（6）的小就往下走，直到找到要找的数字（6）为止，如下图所示：
//杨氏矩阵...
09:53 29人阅读 评论(0) 收藏 举报
问题：已知一个2维矩阵，其中的元素每一行从左至右依次增加，每一列从上到下依次增加。即对于矩阵Table有Table[i]...
int find_data(int arr[][5], int line, int k)
assert(arr);
if ((karr[line - 1][4]))
//有一个二维数组.----杨氏矩阵
//数组的每行从左到右是递增的，每列从上到下是递增的.
//在这样的数组中查找一个数字是否存在。
//时间复杂度小于O(N);
行列递增矩阵的查找
在一个m行n列的二维数组中，每一行都按照从左到右递增的顺序排列，每一列都按照从上到下递增的顺序排列。现输入这样的一个二维数组和一个整数，请完成一个...
杨氏矩阵，即在一个二维数组中，每一行都按照从左到右严格递增的顺序排序，每一列都按照从上到下严格递增的顺序排序。请完成一个函数，输入这样的一个N*N的二维数组和M个整数，判断数组中是否含有上...
他的最新文章
讲师： 许鹏
讲师：董付国
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)即对于矩阵Table有Table[i][j] ≤Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]，我们也称这样的矩阵为杨氏矩阵。
给出判定某个数是否存在该矩阵中的高效算法。
为了便于复杂度分析，我们暂时假定该矩阵为大小n*n。如下图所示为一个杨氏矩阵。
二分搜索解法：
许多人都观察到了矩阵在二维上都是有序的，所以使用在每一行（或者每一列）使用二分搜索是很自然的想法。由于每一行二分搜索需要O(lgn)时间，搜索n行需要O(nlogn)的时间。显然这个时间复杂度还是不够高效。当然这只是第一步尝试，不要让自己过早的陷入到二分搜索的泥潭中，好的方法还在后面。
一种错误的想法：
如果不细心也许会掉入一个陷阱中。有人也许认为可以先从行来判定，如果某个数位于某2行间，则只需要检查相应的2列即可，这是错误的。如下左边图所示，假定我们需要查找9是否在矩阵中，由于9位于7到11之间，所以接下来在7和11的这两列中（这2列在图中高亮显示）二分查找9，虽然能够查找到9，虽然查找9成功了，但是这个方法是错误的。因为10也位于7到11之间，但是10并不在这2列中。
即便是如下右边图示查询范围包括2行2列，尽管在查找9和10都成功，但是还是错误的，反例大家可以自己找一个。
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
Step-wise线性搜索解法：
从右上角开始，每次将搜索值与右上角的值比较，如果大于右上角的值，则直接去除1行，否则，则去掉1列。如下图显示了查找13的轨迹。首先与右上角15比较，13&15，所以去掉最右1列，然后与11比较，这是13&11，去掉最上面1行…以此类推，最后找到13。算法复杂度O(n)，最坏情况需要2n步，即从右上角开始查找，而要查找的目标值在左下角的时候。
四分分解算法：
通过观察很容易发现该题可以使用分治法来解决。可以看到，矩阵的中间元素总是将矩阵分成了4个子矩阵。如下图所示，中间元素9将矩阵分成了4个小矩阵,这4个小矩阵在行和列上面都是排好序的，所以原问题可以分解为4个子问题。进一步观察可以发现，每次可以排除掉1个子矩阵，也就是说只要考虑3个子问题即可。如查找目标元素为13，则13&9，因为左上角的子矩阵都小于9，所以左上角的子矩阵可以不用再查询，只需要查询剩下的3个子矩阵即可。同理，当查找元素为6时，由于6&9，因为右下角的子矩阵都大于9，因此可以直接排除右下角的子矩阵，只需要查询其他3个子矩阵即可。当然，如果中间元素等于查询的目标元素，则直接返回即可，否则在剩下的3个子矩阵中查询。
该算法代码如下,注意边界条件，代码中加粗的部分不可省略，否则会导致代码不可终止。l==r&&u==d表示矩阵中只有一个元素，此时若不等于目标元素target，则必须返回false。
该算法复杂度是多少呢？可以通过公式计算：
原文公式：&T(n) = 3T(n/2) + c, T(n) = 3T(n/2) + c,&&& && = 3 [ 3T(n/4) + c ] + c&&& && = 3 [ 3 [ 3T(n/8)& + c ] + c ] + c&&&&& = 3k T(n/2k) + c (3k - 1)/2&&
= 3k ( T(n/2k) + c ) - c/2&Setting k = lg n,& T(n)& = 3lg n ( T(1) + c ) - c/2&&&&&& = O(3lg n)&&&&&& = O(nlg 3)&&&&&&&&&
&== 3lg n = nlg 3 &&&&& = O(n1.58)&
注：我以为这里公式应该是T(n) = 3 * T(n/4) + c ，不对的话请大家指正。
二分算法：
这个算法我们从矩阵中间行或者中间列或者对角线开始查找，找到s满足
&ai & s & ai+1 ,& 其中ai为矩阵中的值。
a）从中间行查找，如查找10位于9到16之间。
b）从中间列查找，如查找10位于9到14之间。
c）从对角线查找，查找10位于9到17之间。
显然不管从哪里查找，都可以将原矩阵分成2个子矩阵，这样就分成了2个子问题，比起四分分解法的3个子问题，这个方法应该更好。
代码如下，注意这里代码确定范围用的是线性查找，实际可以通过二分查找加速整个过程。
该方法复杂度的分析：为了方便，假定最后查找的子矩阵为分成了2个相同大小的子矩阵,且都为原来1/4大小。
T（n)&=&2T(n/4)+cn&
如果采用二分查找确定范围，则T(n)=2T(n/4)+clgn
英文原文地址：
本文已收录于以下专栏：
相关文章推荐
09:53 29人阅读 评论(0) 收藏 举报
问题：已知一个2维矩阵，其中的元素每一行从左至右依次增加，每一列从上到下依次增加。即对于矩阵Table有Table[i]...
今天碰到了这一问题，考虑的是根据杨氏矩阵的性质，从左到右，从上到下都是递增排序的。因此想要找到杨氏矩阵当中是否存在某数，可以从右上角的数开始找起，即从
Y_Matrix[0][columns-1]开...
人生苦短，都说必须python，那么我分享下我是如何从小白成为Python资深开发者的吧。2014年我大学刚毕业..
问题：已知一个2维矩阵，其中的元素每一行从左至右依次增加，每一列从上到下依次增加。即对于矩阵Table有Table[i][j] ≤Table[i][j + 1], Table[i][j] ≤ Tabl...
先看一个来自算法导论习题里6-3与剑指offer的一道编程题（也被经常用作面试题，本人此前去搜狗二面时便遇到了）：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺...
//来源于算法导论思考题 6-3
一个m*n的Yong式矩阵（Yong tableau） 是一个m*n矩阵，其中的每一行的数据都是从左到右排序，每一列的数据都是从上到下排序。Yon...
在一个M行N列的二维数组中
在一个二维数组中，每行都按照从左到右的递增的顺序排序。每列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个数组和一个数，判断数组中是否包含这个数。
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
    例如下面的二维数组就是...
杨氏矩阵，即在一个二维数组中，每一行都按照从左到右严格递增的顺序排序，每一列都按照从上到下严格递增的顺序排序。请完成一个函数，输入这样的一个N*N的二维数组和M个整数，判断数组中是否含有上...
原帖在此;http://blog.csdn.net/michealmeng555/article/details/2489923
算法研讨的论文【原创分享】
杨氏矩阵 Young Tableau
...
他的最新文章
讲师： 许鹏
讲师：董付国
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)博客访问： 33187
博文数量： 14
博客积分： 1455
博客等级： 上尉
技术积分： 150
注册时间：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
这里就不介绍什么是杨氏矩阵了，直接给出一个杨氏矩阵查找算法的例子，然后反思下自己的思维能力，也总结提高下自己的分析能力，希望可以从今天这个简单的问题上学到更多。
引子：之前算法期末考试出过一个题目，有一个矩阵类似下面这个样子，行从左到右越来越小，列从上到下越来越大，让你找一个元素x,如何在O（n)时间内找到，n表示行列个数总和，如下，找9
10&6&4&2 0
12&7&6&3 1
13&8&7&5 2
这种情况下，可以从左上角开始比较，如果比x大，那么第一列都得去除，变成
接着从左上角比较，如果小，就把第一行去除，
再比较，比9小，去除第一行
再比较去除8，去除7，5，2
这样的话每次去除最多一行或者一列，时间复杂性是O(m+n)。
接着同学问了个杨氏矩阵的问题，如下矩阵，如何查找9
&1 &3 &4 &5 &7 10&2 &4 &7 12 13 15&4 &5 &8 13 14 16&6 &8 10 15 17 19&8 10 12 16 18 2111 12 15 19 20 22
这个时候，傻了，发现恩，跟刚才的不一样，这下是分布不对，就直接说不会。。。。。。
回过头来再看看，不就是把上边的矩阵来个置换吗，怎么就不会了呢？
这次是碰巧想到吗，怎么逆转都想不到，要如何避免，如何锻炼呢？？？
有时候应该尝试着把题目问题距离形象化处理，注意观察，换种思路。
阅读(3712) | 评论(0) | 转发(0) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
图1-1 则现在讨论，这个数据结构的几种操作，而在这些操作中，我们会发现堆排序的影子，并且这些操作具有很好的时间复杂度。 & 条件：一个已经建好的杨氏矩阵（Young Tableau） 操作： 【1】在杨氏矩阵中插入元素x ---- Insert(x) 【2】在杨氏矩阵中删除位于 (x, y) 位置的元素---- Delete(x, y) 【3】返回x是否在矩阵中----Find(x) 其中1-2操作类似于堆的操作，而4操作类似于BST的操作。下面我就用我 自己的理解把这几个操作加以解释。 【1】插入操作 本操作的时间复杂度为O( n + m ),其操作类似于堆排序的SIFT-UP算法(具体算法见《算法设计技巧与分析》 M.H,Alsuwaiyel 著)。它的堆的结构在这里表现为某个元素Y[x, y] 下面和右面的两个元素 Y[x, y+1] ,Y[x+1, y]均比Y[x, y]要大。于是其插入算法可以描述为，首先把待插入元素以行为主序置于所有有效数字（除了无穷以外的数）最后面，如将x=2，放入 图1-1 的d5的位置，然后执行类似于SIFT-UP的操作，将x与它左边（记为x-l）及上面（记为x-u）的数进行比较，根据比较结果有三种可能的操作： 1：x-u & x 且x-u &= x-l& 则将x 与 x-u进行交换 2：x-l & x 且x-l & x-u& 则将x 与 x-l进行交换 3: x &= x-l 且 x & x-u& 则x 不动，此时已经插入成功 （可以有其他合理的约定） 对例子插入2进行操作如图1-2箭头的操作方向。
图1-2 && 由上述的操作知其时间复杂度最大为行列之和，即O(m+n)。 【2】删除操作 操作类似于插入操作，其时间复杂度也为O(m+n)。其操作类似于堆排序的SIFT-DOWN算法。删除算法可以描述为，首先将删除的位置(x, y)的数字删除，然后调整，把杨氏矩阵中的最大值k（可以行为主序进行搜索到最后）填入到被删除位置，然后让此数与其下面的数(k-d)和右面的数进行(k-r)比较,此时比较结果为两种，因为此时元素一定会下移： & 1：k-d & k-r 将k-r 和 k进行交换 & 2：k-d & k-r 将k-d 和 k进行交换 举例 删除图1-1的a3位置的元素5如图1-3
图1-3 & 由操作知，删除算法时间复杂同样最多为行列之和，即O(m + n)。 &&& 【3】查找算法 &&& 查找算法类似于BST二叉排序树，不过需要在其思想上稍微进行修改，才能满足杨氏矩阵的查找操作，同样利用杨氏矩阵的性质，不过此时应该换一个角度思考问题，因为与BST二叉排序树类比，所以应该从左下角开始看起（如 图1-1d1位置），该元素的上面的元素比本身小和右面的元素比本身大，这样就与BST二叉排序树具有相同的性质。所以在查找时从左下角不断的比较，从而最终确定所查找元素位置。 &&& 如查找19，比较顺序如图1-4 &
图1-4 & 此算法的时间复杂度同前两个算法，复杂度也是O(m + n)。-----------------------------------------------------------------------------------------------------------------------------------------------------------杨氏矩阵第k大问题？？/datastructure-and-algorithm/array/matrix/young-tableau-problem/【方案一】 &小顶堆法& 首先将a[0][0]加入小顶堆，然后每次从小顶堆中取出最小元素，并加入比该元素大且与之相邻的两个元素（对于a[0][0]，则需要加入 a[0][1]和a[1][0]），直到取出第k个元素，需要注意的是，需要采用额外空间记录某个元素是否已经加入到小顶堆以防止重复加入。 【方案二】 &二分枚举+类堆查找& 首先，二分枚举找到一个数x，它比杨氏矩阵中k个数大；然后，利用类堆查找法找到刚好小于x的元素。该算法的时间复杂度为O((m+n)lg(mn))，但不需要额外存储空间。代码如下：int find_kth_in_YoungTableau(int** a, int m, int n, int k) {
int low = a[0][0];
int high = a[m-1][n-1];
int order = 0;
int mid = 0;
mid = (low + high) && 1;
order = get_order(a, m, n, mid);
if(order == k)
else if(order & k)
high = mid - 1;
low = mid + 1;
} while(1); //二分枚举整，找出正好大于k的一个整数 mid
int row = 0;
int col = n - 1;
int ret = mid;
while(row &= m-1 && col &= 0) { //找出比mid小的最大数
if(a[row][col] & mid) {
ret = (a[row][col] & ret) ? a[row][col] : ret;
return ret; } & //整数k在矩阵中的排名 int get_order(int** a, int m, int n, int k) {
int row, col, order;
col = n-1;
order = 0;
while(row &= m-1 && col &= 0) {
if(a[row][col] & k) {
order += col + 1;
return order; }
阅读(768)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'杨氏矩阵Young Tableau',
blogAbstract:'原文链接：http://blog.csdn.net/michealmeng555/article/details/2489923 杨氏矩阵（Young Tableau）是一个很奇妙的数据结构，他类似于堆的结构，又类似于BST的结构，对于查找某些元素，它优于堆；对于插入、删除它比BST更方便。 首先介绍一下这个数据结构的定义，Young Tableau有一个m*n的矩阵',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:9,
publishTime:9,
permalink:'blog/static/',
commentCount:0,
mainCommentCount:0,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}}