现在的位置: 首页 > 综合 > 正文

杨氏矩阵查找

2012年03月07日 ⁄ 综合 ⁄ 共 1251字 ⁄ 字号 评论关闭

1. 简述

    杨氏矩阵中,每行元素是递增的,每列元素也是递增的。即a[i][j]<a[i+1][j]且a[i][j]<a[i][j+1]。要在这样的矩阵中查找某个数值元素的位置,复杂度可以达到O(M+N),其中M为矩阵行长度,N为矩阵列长度。

2. 原理

    从矩阵的左下角或者矩阵的右上角处开始递归运行,以左下角为例,value为要查找的值,(i,j)为当前矩阵中的位置,初始为(M-1, 0)。
    如果超过了矩阵范围则说明不存在这样的元素,返回-1,-1。
    否则的话,如果当前位置的值大于value,说明要移动位置,使得数值减小,即递归使得i=i-1;如果当前位置的值小于value,说明要移动位置,使得数值增大,即递归使得j=j+1;如果刚好等于value,返回当前的位置i,j即可。

3. 代码

#include <iostream>
using namespace std;

#define M 5
#define N 4
int array[M][N] = {1,2,3,4,  5,6,7,89,10,11,1213,14,15,1617,18,19,20};

void find_from_left_bottom(int*a, int i,int j, int m, int n, int value, int& x, int& y) {
  
if(i<0 || j>=n)
    x 
= y = -1;
  
else {
    
if(*(a+i*n+j) < value) 
      find_from_left_bottom(a, i, j
+1, m, n, value, x, y);
    
else if(*(a+i*n+j) > value)
      find_from_left_bottom(a, i
-1, j, m, n, value, x, y);
    
else 
      x 
= i, y = j;
  }
}
int main() {  
  
int x,y;
  
int value = 12;
  find_from_left_bottom(array[
0], M-10, M, N, value, x,y);
  cout 
<< x << "  " << y << endl;
  cout 
<< array[x][y] << endl;
  system(
"PAUSE");
  
return 0;

4. 备注

    最初遇到这道题的时候,纠结于把矩阵斜过来看,想用二分的方法,结果没成功。还是老魏同学找到这个方法给我说明的。
    另外,二维数组传递的时候,传int*就好了,反正通过函数传递后,数组的结构信息都会丢失,取得的就是普通的int *而不是行指针了,可以放心大胆的用*(a+i*n+j),要注意其中的n是j下标对应的长度哦。

5. 参考

    杨氏矩阵算法和思维    http://www.cublog.cn/u3/119410/showart_2348130.html

抱歉!评论已关闭.