剑指Offer——二维数组中的查找

发布时间:2017-7-9 7:36:08编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"剑指Offer——二维数组中的查找 ",主要涉及到剑指Offer——二维数组中的查找 方面的内容,对于剑指Offer——二维数组中的查找 感兴趣的同学可以参考一下。

Question

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

Solution

  • 这题的技巧性比较强,因为最右上角的那个数字是这一行最大的,这一列最小的,所以可能将目标值和它进行比较,如果目标值比它小,就可以将所在列去掉,如果目标值比它大,就可以将所在行去掉。

  • 每次比较都可以去掉一行或者一列,所以时间复杂度为O(n + m),n和m分别表示行数和列数

  • 如果单纯遍历数组的话,时间复杂度为O(n * m)

Code

class Solution {public:    bool Find(int target, vector<vector<int> > array) {        if (array.size() == 0)            return false;                int i = 0;        int j = array[0].size() - 1;        while (i < array.size() && j >= 0) {            if (array[i][j] == target)                return true;            // 去掉列            else if (array[i][j] > target)                j--;            // 去掉行            else                i++;        }


上一篇:【slighttpd】基于lighttpd架构的Server项目实战(6)—预备知识之Http

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款