剑指offer——02二维数组中的查找

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

注意：

　数组不一定是这样的：

　　1　　2　　3　　

　　4　　5　　6

　　7　　8　　9

而是这样的：
　　1　　2　　8　　9

　　2　　4　　9　　12

　　4　　7　　10　　13

　　6　　8　　11　　15

一下给出两种方法：

笨方法：

　　从数组左上角开始查找，若target比自己大且比右边的数小，或者比最右边列的数大，则应向下查找，

　　但到达下一行，可能比该数大，则应向改行的右边找，或比该数小，则向左找，这样导致代码判断繁琐

优化：

　　不要只会从左上角的数开始查找，观察数组之后，我们发现，每个数的右下方的数一定比自己大

　　那么就从右上角开始查找，target比自己小时，则向右查找，否则向下查找，这样么每次移动只考虑向左或向右，逻辑简单明了

 class Solution {

 public:

     bool Find(int target, vector<vector<int>> array) {

         int px = array.size(), py = array[].size();

         if (px== || py ==  ||target<array[][] || target>array[px - ][py - ])return false;

         for (int x = , y = ; y < py && x < px &&y >=  && x>=;)

         {

             if (target == array[x][y])return true;

             else if ((y == py- && target > array[x][y])||(y < py -  && target < array[x][y + ] && target > array[x][y]))

                 ++x;

             else if (target < array[x][y])

                 --y;

             else

                 y++;

         }

         return false;

     }

 };

 class Solution {

 public:

     bool Find(int target, vector<vector<int>> array) {

         int px = array.size(), py = array[].size();

         if (target<array[][] || target>array[px - ][py - ])return false;

         int x = , y = py - ;

         while (x < px && y >= )

         {

             if (target == array[x][y])return true;

             else if (target > array[x][y]) ++x;

             else if (target < array[x][y]) --y;

         }

         return false;

     }

 };

巴特西

剑指offer——02二维数组中的查找

题目描述

最新文章

热门文章