算法-二维数组中的查找

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

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

相关文章

来自专栏闻道于事

JavaScript数字例子,二分法,冒泡排序

先看一下两个例子: 十个成绩,求总分,最高分,最低分 //输入10个成绩,求总分,最高,最低 var arr=new Array(67,45,5...

2865
来自专栏desperate633

LintCode 排颜色 II题目分析代码

给定一个有n个对象(包括k种不同的颜色,并按照1到k进行编号)的数组,将对象进行分类使相同颜色的对象相邻,并按照1,2,...k的顺序进行排序。

772
来自专栏技术博客

JavaScript将iframe中控件的值传到主页面控件中

主要是通过在主页面定义一个传输数据的函数GetData(data),然后在iframe嵌入页面中通过parent.GetData(data),这样即可在GetD...

774
来自专栏前端儿

n-1位数

已知w是一个大于10但不大于1000000的无符号整数,若w是n(n≥2)位的整数,则求出w的后n-1位的数。

711
来自专栏机器学习算法全栈工程师

动态规划系列之最长递增子序列问题解答

今天和大家分享的是动态规划经典问题:最长递增子序列问题解答。(似乎BAT等各大公司都喜欢在面试的时候对动态规划系列经典问题进行笔试。 题目描述: 给定一个整数序...

2937
来自专栏GIS讲堂

postgis常用函数介绍(二)

通过函数st_isempty(geom)可以判断geometry是否为空,返回是布尔型的true或者false,具体使用如下:

903
来自专栏xingoo, 一个梦想做发明家的程序员

快速排序

算法思想:对于输入的子数组a[p:r],按下面三个步骤: 1 分解:以a[p]为基准元素将a[p:r]分成三段,a[p:q-1],a[q],a[q+1:r],使...

1939
来自专栏Java Edge

美团18春招编程笔试题赏析1 字符串距离2 数字字符

2808
来自专栏java一日一条

MySQL函数大全及用法示例(二)

数学函数 abs(n) 返回n的绝对值 mysql> select abs(2);   -> 2 mysql> select abs(-...

904
来自专栏nummy

numpy入门

numpy中最主要的对象是同质数组array,也就是说数组中的元素类型都是一样的。数组的维度也称之为axis,axis的的个数称之为秩rank。

712

扫码关注云+社区