当前位置:首页 » 面试笔试 » 正文

程序员面试题-二维数组中的查找

1853 人参与  2019年03月01日 16:27  分类 : 面试笔试  评论

题目描述

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

image.png

image.png

解题思路:

比如在上图的二维数组中查找元素7,我们每次查找都使用当前数组右上角那个元素与目标元素作比较。比如第一次选右上角的9与7对比,7小于9,显然,9所在那一列不可能有7了,因为那一列最小的元素是9,7比9还小。我们就剔除了这一列!

接下来,数组右上角的元素就变为8了,7比8小,因此再剔除这一列。此时数组右上角元素为2了,7比2大,那就剔除2所在的行,这是因为2是在这行的最右边,是这行的最大的元素,7比2大,就比这行所有元素都大,所以剔除这一行。

总结一下上面的思路:

当target == 当前数组右上角元素时,找到元素,返回。

当target < 当前数组右上角元素时,剔除当前数组右上角元素所在这一列。

当target > 当前数组右上角元素时,剔除当前数组右上角元素所在这一行。

正确的代码如下:

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int row,column;
        row = 0;
        column = array[0].size()-1;
        while(row < array.size() && column >=0)
        {
            if(target == array[row][column])
            {
                return true;
            }
            else if(target < array[row][column])
            {
                column--;
            }
            else
            {
                row++;
            }
        }
        
        return false;
    }
};



来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=1222

数据结构习题解析  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!