算法 查找 【剑指 Offer 04 二维数组中的查找】

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法 查找 【剑指 Offer 04 二维数组中的查找】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2246字，纯文字阅读大概需要4分钟。

内容图文

一、题目描述

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

 

示例:

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false。

限制：

0 <= n <= 1000

0 <= m <= 1000

 

二、思路

最简单的思路肯定是一一遍历。但是这样的时间复杂度很高，我们需要设计一个更高效的算法，所以需要先研究该二维数组：

题目中有这样一句话：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

也就是说，右上角的元素是第一行元素中最大的，同时是最后一列元素中最小的。

右上角元素的左边第一个元素是第一行元素中次大的，同时是倒数第二列元素中最小的。

整理可得：第一行第m列元素是第一行第m大的，同时是第m列中最小的。

那么我们可以拿目标和第一行最后一列的元素进行比较，比较顺序为从右至左。

举个例子：

假如我们要找8，8比15小，说明8所在的列在15所在列的左侧，那么接下来和11比；

8比11小，说明8所在的列在11所在列的左侧，那么接下来和7比；

8比7大，证明如果矩阵中存在8，那么8肯定与7同列，且在7的下方。那么接下来将行增加一行，进行比较；

最终找到了8。

那么对于找不到的元素呢？

我们可以设置一个循环，假设一开始就找不到，设置一个flag = 0；如果找到了就设置flag = 1，然后跳出循环；

如果还是找不到，那么需要一个结束循环的条件：行超过了最大行，或者列为负数。

 

三、代码

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        bool found = false;
        //如果数组为空，肯定找不到
        //一共matrix.size()行
        //matrix[0].size()列
        if (matrix.empty())
        {
            return found;
        }
        //最大行
        int rows = matrix.size();
        //最大列
        int columns = matrix[0].size();

        //当前元素从右上角开始
        //当前行设置为0
        int row = 0;
        //当前列设置为列的边界，因为数组下标从0开始，所以边界为最大列-1
        int column = columns-1;
        //循环条件：行没有超过最大行，列没有为负数
        while (row < rows && column >= 0)
        {
            //如果找到目标，即返回
            if (target == matrix[row][column])
            {
                found = true;
                break;
            }
            //如果目标比当前元素小，而当前元素又是该列中最小的，所以往左缩短一列
            else if (target < matrix[row][column])
            {
                column--;
            }
            //如果在目标元素已经小于右边所有元素的情况下，目标元素又比当前元素大，说明目标元素在当前元素下方，所以往下增加一列
            else
            {
                row++;
            }
        }
        return found;

    }
};

 

 

 

 

 

内容总结

以上是互联网集市为您收集整理的算法 查找 【剑指 Offer 04 二维数组中的查找】全部内容，希望文章能够帮你解决算法 查找 【剑指 Offer 04 二维数组中的查找】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---