每天一道劍指offer-二維數組中的查找

• 2019 年 10 月 4 日
• 筆記

題目

每天一道劍指offer-二維數組中的查找 中文鏈接： http://t.cn/RdKlvjM

題目詳述

在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

題目詳解

思路

• 劍指offer的思路.就是比較矩陣的右上角的數與target的大小，如果target比這個矩陣右上角的數大，由於矩陣的右上角元素A是A所在行的最大的值，所以target肯定不在A所在的行了，所以這時候就應該就在除去第一行的剩下的行中去找這個target;
• 如果target比矩陣右上角的數A小，那麼由於A所在的列中A是最小的，那麼target就在除去最右邊的列的其它的列； 如果相等，返回true;

public class Solution {      public boolean Find(int target, int [][] array) {          if(array.length == 0 || array[0].length == 0  )              return false;          int rows = array.length-1;          int cols = array[0].length-1;          int i = 0;          int j = cols;          while(i <= rows && j >= 0)          {              if(array[i][j] < target)              {                  i++;              }else if(array[i][j] > target)              {                  j--;              }else{                  return true;              }          }          return false;      }  }  

代碼講解

• 11-13行就是 右上角比target小，只能i++進入下一行
• 14-16行就是 右上角比target大，只能j–進入到左邊的這些列