当前位置: 代码迷 >> 综合 >> 二维矩阵(杨氏矩阵)查找 、定义: 从左到右,从上到下,依次增大的矩阵
  详细解决方案

二维矩阵(杨氏矩阵)查找 、定义: 从左到右,从上到下,依次增大的矩阵

热度:53   发布时间:2024-01-04 15:14:27.0

查找某元素

假设矩阵为

                   1     2   8   9

                   2    4    9   12

                   4    7   10  13

                   6    8    11  15

    在里面查找7,如果我们从1开始,则1的右半部分,也就是剩下矩阵的全体,都可能会存在7,这是显然不行的,我们要确定一个确切的查找规则,它沿着特定路线走,最后找到

    我们看其规律,如果说要查找的元素比当前元素大,则在其右半部与下半部   如果比当前元素小,则在其左半部与上半部。

    而如果我们从右上角开始,9开始,查找7,首先7小于9,所以要在其左半部分与上半部分查找,9的上半部分是没有的,左半部分就是第1 2 3 列,第4列排除掉(注意这个排除掉的意思,意思是说7不可能在这里了)

   我们往左走到8,7比8小,同样我们还得往左走,那就是2,

  7比2大,所以我们就找右下两部分,右半部分,第3 4 列,我们其实前面已经排除了,只剩下下边的,于是我们从2开始往下走,走到了4

  ······以此类推

   杨氏矩阵难点在于如何选择起始点,以及为什么要选择这个起始点。这一点一定要搞清楚。

  我们这里找到大于要寻找的元素,不再为向下还是向右犹豫不决了,我们只需要向下,碰到小于要寻找的元素也是如此。

  

[cpp]  view plain copy
  1. #include <iostream>  
  2. #include <algorithm>  
  3. using namespace std;  
  4. int a[4][4]={ {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};  
  5. int k=0;  
  6. bool findElem(int row,int col)  
  7. {  
  8.   while((row>=0&&row<4)&&(col>0&&col<4))  
  9.   {  
  10.     if(a[row][col]=k)  
  11.         return true;  
  12.     if(a[row][col]<k)  
  13.     {  
  14.       row++;  
  15.     }  
  16.     else  
  17.         col--;  
  18.   }  
  19.   return false;  
  20. }  
  21. int main()  
  22. {  
  23.   
  24.   if(findElem(0,3))  
  25.       cout<<"find it"<<endl;  
  26.   else  
  27.       cout<<"could not find it"<<endl;  
  28.   return 0;  
  29. }