即对于矩阵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步,即从右上角开始查找,而要查找的目标值在左下角的时候。
【代码】
-
boolstepWise(intmat[][N_MAX],intN,inttarget,
-
int&row,int&col){
-
if(target<mat[0][0]||target>mat[N-1][N-1])returnfalse;
-
row=0;
-
col=N-1;
-
while(row<=N-1&&col>=0){
-
if(mat[row][col]<target)
-
row++;
-
elseif(mat[row][col]>target)
-
col--;
-
else
-
returntrue;
-
}
-
returnfalse;
-
}
四分分解算法:
通过观察很容易发现该题可以使用分治法来解决。可以看到,矩阵的中间元素总是将矩阵分成了4个子矩阵。如下图所示,中间元素9将矩阵分成了4个小矩阵,这4个小矩阵在行和列上面都是排好序的,所以原问题可以分解为4个子问题。进一步观察可以发现,每次可以排除掉1个子矩阵,也就是说只要考虑3个子问题即可。如查找目标元素为13,则13>9,因为左上角的子矩阵都小于9,所以左上角的子矩阵可以不用再查询,只需要查询剩下的3个子矩阵即可。同理,当查找元素为6时,由于6<9,因为右下角的子矩阵都大于9,因此可以直接排除右下角的子矩阵,只需要查询其他3个子矩阵即可。当然,如果中间元素等于查询的目标元素,则直接返回即可,否则在剩下的3个子矩阵中查询。
该算法代码如下,注意边界条件,代码中加粗的部分不可省略,否则会导致代码不可终止。l==r&&u==d表示矩阵中只有一个元素,此时若不等于目标元素target,则必须返回false。
-
boolquadPart(intmat[][N_MAX],intM,intN,inttarget,intl,intu,intr,intd,int&targetRow,int&targetCol){
-
if(l>r||u>d)returnfalse;
-
if(target<mat[u][l]||target>mat[d][r])returnfalse;
-
intcol=l+(r-l)/2;
-
introw=u+(d-u)/2;
-
if(mat[row][col]==target){
-
targetRow=row;
-
targetCol=col;
-
returntrue;
-
}elseif(l==r&&u==d){
-
returnfalse;
-
}
-
if(mat[row][col]>target){
-
returnquadPart(mat,M,N,target,col+1,u,r,row,targetRow,targetCol)||
-
quadPart(mat,M,N,target,l,row+1,col,d,targetRow,targetCol)||
-
quadPart(mat,M,N,target,l,u,col,row,targetRow,targetCol);
-
}else{
-
returnquadPart(mat,M,N,target,col+1,u,r,row,targetRow,targetCol)||
-
quadPart(mat,M,N,target,l,row+1,col,d,targetRow,targetCol)||
-
quadPart(mat,M,N,target,col+1,row+1,r,d,targetRow,targetCol);
-
}
-
}
-
-
boolquadPart(intmat[][N_MAX],intN,inttarget,int&row,int&col){
-
returnquadPart(mat,N,N,target,0,0,N-1,N-1,row,col);
-
}
该算法复杂度是多少呢?可以通过公式计算:
原文公式: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/2Setting 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个子问题,这个方法应该更好。
代码如下,注意这里代码确定范围用的是线性查找,实际可以通过二分查找加速整个过程。
-
boolbinPart(intmat[][N_MAX],intM,intN,inttarget,intl,intu,intr,intd,int&targetRow,int&targetCol){
-
if(l>r||u>d)returnfalse;
-
if(target<mat[u][l]||target>mat[d][r])returnfalse;
-
intmid=l+(r-l)/2;
-
introw=u;
-
while(row<=d&&mat[row][mid]<=target){
-
if(mat[row][mid]==target){
-
targetRow=row;
-
targetCol=mid;
-
returntrue;
-
}
-
row++;
-
}
-
returnbinPart(mat,M,N,target,mid+1,u,r,row-1,targetRow,targetCol)||
-
binPart(mat,M,N,target,l,row,mid-1,d,targetRow,targetCol);
-
}
-
-
boolbinPart(intmat[][N_MAX],intN,inttarget,int&row,int&col){
-
returnbinPart(mat,N,N,target,0,0,N-1,N-1,row,col);
-
}
该方法复杂度的分析:为了方便,假定最后查找的子矩阵为分成了2个相同大小的子矩阵,且都为原来1/4大小。
T(n)=2T(n/4)+cn
如果采用二分查找确定范围,则T(n)=2T(n/4)+clgn
英文原文地址:http://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html
分享到:
相关推荐
Strassen矩阵乘法和棋盘覆盖和自然合并排序算法Strassen矩阵乘法和棋盘覆盖和自然合并排序算法Strassen矩阵乘法和棋盘覆盖和自然合并排序算法Strassen矩阵乘法和棋盘覆盖和自然合并排序算法Strassen矩阵乘法和棋盘...
php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵...
邻接矩阵 Prim 算法,C++完美实现,数据结构作业。
这是一款用矩阵分解算法实现的FFT蝶形算法,根据著名的fast algorithm of DCT 1974年的论文实现
矩阵相乘FOX并行算法,矩阵相乘FOX并行算法
常用矩阵数学算法
代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图...
算法分析:对杨氏矩阵问题进行了深入的算法分析和推理,为解决问题提供了理论支持。 代码实现:提供了完整的代码实现,包括主函数和辅助函数,展示了如何用编程语言解决杨氏矩阵问题。 测试样例:包含了多组测试样例...
稀疏矩阵的压缩存储。 包含算法:快速转置算法、矩阵乘法运算、矩阵加法运算、打印矩阵信息。
矩阵计算中第一次实验题,计算下三角矩阵的逆矩阵的详细算法,可以正常运行,有所有的测试数据与运行结果
算法分析与设计中趣味矩阵的实现源代码!实现的是把有规律的矩阵打印出来。
关于矩阵束算法的MATLAB程序,其中还有有关DOA的有关矩阵束算法
通过矩阵对apriori进行该进,apriori,改进算法,矩阵实现
采用Warshall算法,从邻接矩阵求可达矩阵
代码 无向图关联矩阵和邻接矩阵的相互转换算法代码代码 无向图关联矩阵和邻接矩阵的相互转换算法代码代码 无向图关联矩阵和邻接矩阵的相互转换算法代码代码 无向图关联矩阵和邻接矩阵的相互转换算法代码代码 无向图...
矩阵乘积改进算法 矩阵乘积改进算法 矩阵乘积改进算法 矩阵乘积改进算法
矩阵算法题。这道题主要是类似螺旋的数字排列,从外层1旋转到最中间。 让你更加了解二维数组和矩阵的相关的应用。这里主要是一个逻辑,转过弯就容易了。想了我1天呀。很值得, 很难得,分享给大家,希望对学C的同学...
c#矩阵算法
矩阵 JAVA矩阵 JAVA矩阵 JAVA矩阵 JAVA矩阵 JAVA矩阵 JAVA矩阵 JAVA矩阵 JAVA矩阵 JAVA
矩阵分解的推荐算法 matlab实现,直接运行main.m