剑指offer-二维数组的查找
Peng's Blog 只记录和技术相关的东西

剑指offer-二维数组的查找


面试题3 - 二维数组的查找

题目描述:

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

思路:

这里最重要的一步是:注意右上角的数字。 如果该数字大于要查找的数字,那么剔除这个数字所在的列;如果该数字小于要查找的数字,那么剔除该数字所在的行。

public class Solution {
     public boolean Find(int target, int [][] array) {
          if (array == null || array[0] == null || array[0].length == 0
                    || array.length == 0)
             return false;
          if (array[0][0] > target
                    || array[array.length - 1][array[0].length - 1] < target)
               return false;
          for (int i = 0; i < array.length; i++) {
               if (array[i][0] <= target && array[i][array[0].length - 1] >= target) {
                    int left = 0;
                    int right = array[0].length - 1;
                    int mid = 0;
                    while (left <= right) {
                         mid = left + (right - left) / 2;
                         if (array[i][mid] > target)
                              right = mid - 1;
                         else if (array[i][mid] < target)
                              left = mid + 1;
                         else
                              return true;
                    }
               }
          }
          return false;
     }
 }


上一篇 CVTE & 链家

Comments

评论功能暂停使用,如需跟作者讨论请联系底部的GitHub