【剑指offer】 1、二维数组中的查找

Myth丶恋晨 2022-12-07 01:15 152阅读 0赞

## 二维数组中的查找 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjExODcxNg_size_16_color_FFFFFF_t_70][]

## 解析 ##

很明显，由于该二维数组上到下递增，左到右递增的特殊性，遍历整个矩阵进行查找不是该题目的意图所在。总结规律我们可以发现：应该从矩阵的右上角或者左下角开始查找。

以右上角为例，首先选取右上角的数字，如果该数字**等于**要查找的数字，则查找过程结束；如果该数字**大于**要查找的数字，则说明该列其他元素都大于要查找的数字，便可以删掉该列；如果该数字**小于**要查找的数字，则说明该行其他元素也都小于要查找的数字，便可以删掉该行。

这样，每一次比较都可以剔除一行或者一列，进而缩小查找范围，时间复杂度为O(n)。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjExODcxNg_size_16_color_FFFFFF_t_70 1][]

## Java代码 ##

public class Solution {
        public boolean Find(int target, int [][] array) {
            /*
            思路：从左下角（或者右上角）开始查找，因为该行右边大于它，上边小于它，每次比较可以删除某一        
                 行或者某一列
            注意：左上和右下不可以，因为无法减小问题规模（行和列都无法删除）
            */
            if(array==null)
                return false;
            int row=array.length; //行数
            int col=array[0].length; //列数
            for(int i=row-1,j=0;i>=0&&j<col;){ //从左下角开始查找
                if(array[i][j]==target) //找到
                    return true;
                else if(array[i][j]>target) //不可能在该行，跳过该行
                    i--;
                else //不可能在该列，跳过该列
                    j++;
            }
            return false;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjExODcxNg_size_16_color_FFFFFF_t_70]: /images/20221123/95382776130f46ad9290224e8eb5631d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjExODcxNg_size_16_color_FFFFFF_t_70 1]: /images/20221123/6a7212b8d8ff47cf84328c16505495c6.png