【剑指offer】面试题04 - 二维数组中的查找

清疚 2022-11-02 11:56 151阅读 0赞

### 文章目录 ###

*  面试题 4 ：二维数组中的查找
 *   *  解法一：暴力遍历法
     *  解法二：利用题意 行列排除法

# 面试题 4 ：二维数组中的查找 #

`题目描述`

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

`示例`

> **输入：**
> 
>     7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
> 
> **输出：**
> 
>     true

## 解法一：暴力遍历法 ##

> 思路：
> 
> 1.  逐个遍历所有元素
> 2.  如果与target相等，则返回true
> 3.  如果找不到，则返回false
> 
> 时间复杂度：O( N ^ 2 )
> 
> 空间复杂度：O( 1 )

bool findNumberIn2DArray(vector<vector<int>>& v, int target) 
    { 
        int width = v[0].size();
        int height = v.size();
        if(width == 0 || height == 0) return false;
        for(int i = 0; i < height; i++)
            for(int j = 0; j < width; j++)
                if(v[i][j] == target) return true;
        return false;
    }

## 解法二：利用题意 行列排除法 ##

> **思路：**
> 
>  *  用右上角的数字 x 与 target 进行比较：
>     
>      *  如果 x > target，排除 x 位于的列
>      *  如果 x < target，排除 x 位于的行
>      *  如果 x = target，返回true
>  *  直到越过cols和rows边界时，表示找不到，返回false
> 
> 时间复杂度：O(clos+rows)
> 
> 空间复杂度：O(1)
> 
> **图解：**
> 
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 1]
> 
> **生动的比喻：**
> 
>  *  从右上角看，类似一个斜着的二叉搜索树，右上角为 root，左上都是小的，右下都是大的

bool findNumberIn2DArray(vector<vector<int>>& v, int target)
    { 
        if(v.size() == 0 || v[0].size() == 0) return false;
    
        int rows = v.size();
        int cols = v[0].size();
    
        int col = cols - 1, row = 0;
        while(col >= 0 && row < rows)
        { 
            if(v[row][col] < target)
                row++;
            else if(v[row][col] > target)
                col--;
            else 
                return true;
        }
        return false;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]: /images/20221024/65dd86524ed24bf788517b03d6e8d2d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 1]: /images/20221024/10319abc76c941278e40ffb9572c936f.png