杨氏矩阵查找

╰+哭是因爲堅強的太久メ 2022-05-26 13:25 155阅读 0赞

1. 简述

杨氏矩阵中，每行元素是递增的，每列元素也是递增的。即a\[i\]\[j\]<a\[i+1\]\[j\]且a\[i\]\[j\]<a\[i\]\[j+1\]。要在这样的矩阵中查找某个数值元素的位置，复杂度可以达到o(m+n)，其中n为矩阵行长度，m为矩阵列长度。  
2. 原理  
从矩阵的左下角或者矩阵的右上角处开始递归运行，以左下角为例，key为要查找的值，(i,j)为当前矩阵中的位置，初始为(N-1, 0)。  
如果超过了矩阵范围则说明不存在这样的元素。  
下面， 每行元素从左到右递增，每列元素从上到下递增。  
例如：  
5 5  
2 3 4 5 6  
3 4 5 6 7  
4 5 6 7 8  
5 6 7 8 9  
6 7 8 9 10  
话说杨氏矩阵不存在相同元素，不过这不是重点，有相同元素一样可以查找。。。。

普通的代码如下，复杂度 O(M+N) .

#include<iostream>
    #include<string>
    using namespace std;
    const int MM=1005;
    int map[MM][MM],N,M;
    int search(int x,int y,int key,int &px,int &py){//从矩阵的左下角开始查找
    	if(x<0 || y>=M)
    		return 0;
    	if(map[x][y]<key)
    		return search(x,y+1,key,px,py);
    	else if(map[x][y]>key)
    		return search(x-1,y,key,px,py);
    	else{
    		px=x, py=y;
    		return 1;
    	}
    }
    int main(){
    	while(scanf("%d%d",&N,&M)==2){
    		for(int i=0;i<N;++i) //输入矩阵，N行，M列，下标从0开始
    			for(int j=0;j<M;++j)
    				scanf("%d",&map[i][j]);
    		int key;
    		while(scanf("%d",&key)==1){  // 查找key
    			int px,py;
    			if(search(N-1,0,key,px,py)){ //返回的（px,py)是key在矩阵中的最后一个位置
    				puts("have find");
    				printf("px == %d , py == %d \n",px,py);
    			}
    			else
    				puts("not find");
    		}
    	}
    	return 0;
    }

二分这个矩阵是可以的，效率还高很多，复杂度 O（log(N\*M) )。显然这个效率远比上面那个代码高。  
第一次选中间那个数，设为x，那么x的左上角子矩阵的每个数是小于x的，其他部分可化为3个子矩阵。这样就可以转换为子问题了。  
代码如下：

#include<iostream>
    #include<string>
    using namespace std;
    const int MM=1005;
    int map[MM][MM],N,M;
    int search(int lx,int ly,int rx,int ry,int key,int &px,int &py){ //从矩阵（左上角为（lx,ly)，右下角为（rx,ry)）中查找key
    	int midx=lx+(rx-lx)/2,midy=ly+(ry-ly)/2;
    	if(lx>rx || ly>ry)
    		return 0;
    	if(midx<0 || midx>=N || midy<0 || midy>=M)
    		return 0;
    	if(key==map[midx][midy]){
    		px=midx, py=midy;
    		return 1;
    	}
    	if(midx==0 && midy==0) //
    		return 0;
    	if(key<map[midx][midy])
    		return search(lx,ly,midx,midy,key,px,py);
    	else{
    		if(search(lx,midy+1,midx,ry,key,px,py))
    			return 1;
    		if(search(midx+1,ly,rx,midy,key,px,py))
    			return 1;
    		if(search(midx+1,midy+1,rx,ry,key,px,py))
    			return 1;
    	}
    	return 0;
    }
    int main(){
    	while(scanf("%d%d",&N,&M)==2){
    		 for(int i=0;i<N;++i) //输入矩阵，N行，M列，下标从0开始
    			 for(int j=0;j<M;++j)
    				 scanf("%d",&map[i][j]);
    		 int key;
    		 while(scanf("%d",&key)==1){  // 查找key
    			 int px,py;
    			 if(search(0,0,N-1,M-1,key,px,py)){ //返回的（px,py)是key在矩阵中的最后一个位置
    				 puts("have find");
    				 printf("px == %d , py == %d \n",px,py);
    			 }
    			 else
    				 puts("not find");
    		 }
    	}
    	return 0;
    }

转自： [http://www.darkswordzone.com/?p=1632][http_www.darkswordzone.com_p_1632]

[http_www.darkswordzone.com_p_1632]: http://www.darkswordzone.com/?p=1632