专栏首页深度学习与计算机视觉算法-二维数组中的查找

算法-二维数组中的查找

问题: 在一个二维数组中,每一行元素都按照从左到右递增的顺序排序,每一列元素都按照从上到下递增的顺序排序。实现一个查找功能的函数,函数的输入为二维数组和一个整数,判断数组中是否含有该整数。 解题思路: 比如一个二维数组是这样:

要查找数组7在不在数组内,根据前人总结出来的规律,我们可以这样做: 选择从数组的右上角的点开始比较,此时该值为9,9>7,同时9还是第四列最小的数字,那么这意味着,第四列都不可能找到7,于是我们可以直接删除第四列。

绿色代表所在的行或者列已经排查完了,红色代表当前值。此时值为8,显然和之前的结果一样。

然后我们比较2与7,2<7,同时2的位置是当前行内最大的数值,这意味着该行内不可能找到7,于是删除该行:

4与2的情况相同,直接删除该行:

最后我们找到了7。

这个思路关键的地方在于右上角点的选取,因为这个点的值是所在列的最小值和所在行的最大值,这就意味着: 要查找的数值如果比右上角的值大,那么它将大于整个行; 要查找的数值比如果右上角的值小,那么它将小于整个列。 如果相等的话,查找就结束了~~~

所以无论是哪一种情况,都可以让我们删除一个行或一个列,下一次要比较的那个值就是删除后的二维数组的右上角的值,总之永远在用右上角的值在比较。

这个一个最大一个最小的特性,除了右上角的点之外,左下角也是满足的。

代码实现

bool Find(int* matrix, int rows, int columns, int number)
{
    bool found = false;

    if(matrix != NULL && rows > 0 && columns > 0)
    {
        int row = 0;
        int column = columns - 1;
        while(row < rows && column >=0)
        {
            if(matrix[row * columns + column] == number)
            {
                found = true;
                break;
            }
            else if(matrix[row * columns + column] > number)
                -- column;
            else
                ++ row;
        }
    }

    return found;
}

在上面的代码中有一个地方需要注意一下,二维数组取值的方式用的是这样:matrix[row * columns + column],这是因为我们把二维数组作为参数传递了,参数传递时将二维数组的强制转换为一维指针,这就相当于把二维数组按照行连起来,连接成一个一维数组,那么matrix[row * columns + column]不就是对应二维数组中的第row行,第column列的那个数么。注意row和column是从0开始的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 非极大值抑制(Non-Maximum Suppression)

    博客:noahsnail.com  |  CSDN  |  简书 |   云+社区

    Tyan
  • 腾讯赵建春:AI浪潮下的高效运维思考及实践

    腾讯 SNG 助理总经理、GOPS 金牌讲师赵建春老师受邀出席大会,并带来精彩演讲《AI 浪潮下的高效运维思考与实践》。

    织云平台团队
  • 京东首届”JDD-2017京东金融全球数据探索者大赛”中国区算法组落下帷幕

    2月17日,在经历了48小时的极限挑战之后,首届”JDD-2017京东金融全球数据探索者大赛”算法组全球总决赛和商业组中国区决赛落下帷幕。算法组四大赛题冠军分别...

    人工智能的秘密
  • 深度学习与强化学习

    随着 DeepMind 公司的崛起,深度学习和强化学习已经成为了人工智能领域的热门研究方向。除了众所周知的 AlphaGo 之外,DeepMind 之前已经使用...

    张戎
  • 让大象起舞:HTTPS 计算性能优化

    HTTPS 很安全,与此同时却又要消耗非常多的CPU资源,STGW 针对 nginx 和 openssl 进行了大量优化,用以提升 HTTPS 的计算性能和访问...

    腾讯技术工程官方号
  • 15个顶级Java多线程面试题及答案

    在任何Java面试当中多线程和并发方面的问题都是必不可少的一部分。如果你想获得任何股票投资银行的前台资讯职位,那么你应该准备很多关于多线程的问题。在投资银行业务...

    Java后端工程师
  • 算法:大O符号解释

    O(n),O(1),O(log n)等大O符号被用来表示算法的效率。在这篇文章中,你会找到每个大O符号的例子和解释。

    大数据弄潮儿
  • FPGA : 用“芯”做图

    图像的压缩,从本质上是通过提高计算算力来降低存储和带宽。同时更加复杂的算法也带来计算算力的大量消耗和处理延时的增加。

    腾讯架构师
  • 神经网络模型求解思路

    神经网络模型,mini_batch 批梯度下降(SGD)求解权重参数的原理见:深度学习|神经网络模型简介和梯度下降求解,这篇文章中用一个小球下坡,解释了各个节点...

    人工智能的秘密
  • 全面、简单理解朴素贝叶斯(Naive Bayes)

    朴素贝叶斯(Naive Bayes)是经典的机器学习算法之一,也是为数不多的基于概率论的分类算法。本文可能是目前网络上最全面也最简单易懂的有关朴素贝叶斯的文章。

    挖掘大数据

扫码关注云+社区

领取腾讯云代金券