题解 | #1. 二维数组中的查找#

解题思路

1. 判断右上角数字与目标大小
   1. 如果右上角大于目标,剔除最后一列
   2. 如果右上角等于目标返回true
   3. 如果右上角小于目标,剔除第一行
2. eg
   1. 目标6,初始矩阵如图

           1 2 8 9
           2 4 9 12
           4 7 9 12
           6 8 11 15

   2. 9>6,剔除最后一列,查找区域为

           1 2 8 
           2 4 9 
           4 7 9 
           6 8 11 

   3. 8>6,剔除最后一列,查找区域为

           1 2  
           2 4 
           4 7  
           6 8 

   4. 2<6,剔除第一行,查找区域为

           2 4 
           4 7  
           6 8 

   5. 4<6,剔除第一行,查找区域为

           4 7  
           6 8 

   6. 7>6,剔除最后一列,查找区域为

           4  
           6  

   7. 4<6,剔除第一行,查找区域为

         6 

   8. 6=6,查找结束,返回true
   9. 若目标为5,5<6,剔除第一行,行数越界,查找结束,返回false

代码

public class Solution {

    public boolean Find(int target, int [][] array) {

        /*
        * 思路
        *   判断右上角数字与目标大小
        *       如果右上角大于目标,剔除最后一列
        *       如果右上角等于目标返回true
        *       如果右上角小于目标,剔除第一行
        * */

        // 特殊情况
        if (array==null){
            return false;
        }

        // 初始右上角元素
        int row = 0, column = array[0].length-1;

        // 当行数列数越界时结束循环
        while (row<=array.length-1 && column>=0){

            if (array[row][column]>target){
                column--;
            }else if (array[row][column]<target){
                row++;
            }else if (array[row][column]==target){
                return true;
            }

        }

        return false;

    }

}