算法-二维数组中的查找

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

要查找数组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 条评论
登录 后参与评论

相关文章

来自专栏陈树义

BitMap 算法

什么是 BigMap 算法 所谓 BitMap 就是用一个 bit 位来标记某个元素对应的 value,而 key 即是这个元素。由于采用bit为单位来存储数据...

2916
来自专栏我是业余自学C/C++的

Remove Duplicates from Sorted Array II

1444
来自专栏无所事事者爱嘲笑

常用的sort打乱数组方法真的有用?

1796
来自专栏我是业余自学C/C++的

矩阵

1285
来自专栏社区的朋友们

sizeof 知多少? (上)

稍熟悉 C/C++ 的朋友,对于 sizeof 肯定不陌生,通过它我们可以知晓某个类型或者实例的内存大小( 以字节计 ),网上关于这个话题的信息其实挺多的,但是...

1140
来自专栏我杨某人的青春满是悔恨

“身首异处”的序列(Swift)

声明:文章开头部分内容翻译自objc的一篇博客。当然,我并没有逐行翻译原文,只是说个大致意思,顺带阐述一些自己的理解和扩展思考,还有我自己的代码。

902
来自专栏和蔼的张星的图像处理专栏

165. 合并两个排序链表双指针

将两个排序链表合并为一个新的排序链表. 样例 给出 1->3->8->11->15->null,2->null, 返回 1->2->3->8->11->15...

643
来自专栏CDA数据分析师

学会这8个(组)excel函数,轻松解决工作中80%的难题

文 | 兰色幻想-赵志东 函数是excel中最重要的分析工具,面对400多个excel函数新手应该从哪里入手呢?下面是实际工作中最常用的8个(组)函数,学会后工...

1787
来自专栏小樱的经验随笔

【批处理学习笔记】第十七课:截取字符串

    在批处理中,set的功能有点繁杂:设置变量、显示环境变量的名及值、做算术运算、等待用户的输入、字符串截取、替换字符串,是我们常用的命令之一。   在字...

2964
来自专栏CDA数据分析师

Python之numpy数组学习(二)

前言 前面我们学习了numpy库的简单应用,今天来学习下比较重要的如何处理数组。 处理数组形状 下面可将多维数组转换成一维数组时的情形。 利用以下函数处理数组的...

1768

扫码关注云+社区