当前位置:首页 > 高性能开发 > 数据结构与算法

[NewCoder 三] 二维数组中的查找

优良自学吧提供[NewCoder 三] 二维数组中的查找,[NewCoder 3] 二维数组中的查找 题目描述 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。   来分析下,假设在数组中随便找一个数字 inner_nu

[NewCoder 3] 二维数组中的查找

题目描述

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

image

 

来分析下,假设在数组中随便找一个数字 inner_number 来与 target 进行比较,如果 target > inner_number,那么我们需要在数组中剔除掉 inner_number 所在行的左边的数、 inner_number 所在列的上边的数以及左上部分的数;同理,如果 target < inner_number,那么我们需要在数组中剔除掉 inner_number 所在行的右边的数、 inner_number 所在列的下边的数以及右下部分的数。

小结一下,

如果 target 大了,那么剔除左上部分的数字

如果 target 小了,那么剔除右下部分的数字

这样一来,要表示数组中剩下的数字就比较蛋疼。如果可以一次剔除掉一行或者一列那就比较爽了,那么有没有这样的办法呢?当然,在一开始将 target 与右上角的数来比较,就可以做到一次剔除一行或者一列。同理,一开始将 target 与左下角的数比较也可以。

Why? 对于右上角的数字,如果 target 大了,那么就剔除左上部分的数字,上面没有东西了,所以就变成剔除该数字所在的行了;如果 target 小了,那么就剔除右下部分的数字,右边没有东西了,所以就变成剔除该数字所在的列了。左下角同理。

但是,左上角的数字与右下角的数字不可以。按左上角的数字来举例。如果 target 大了,那么剔除左上部分,特么左边与上边都没了,就只能剔除自己,这也太蛋疼了…当然 target 小了是好办,一下子把数字都剔除光了,返回 false 。

来看代码:

class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        
        int maxRow = array.size() - 1;
        int minCol = 0;
        
        int curRow = 0;
        int curCol = array[0].size() - 1;
        
        // 从右上角开始查询,一次删除一行或者一列
        while (curRow <= maxRow && curCol >= minCol) {
            if (array[curRow][curCol] == target) {
                return true;
            } else if (array[curRow][curCol] < target) {
                curRow++;
            } else {
                curCol--;
            }
        }
        
        return false;   
    }
};

顺带写个递归版本玩玩:

class Solution {
public:
	bool Find(vector<vector<int> > array,int target) {
        int maxRow = array.size() - 1;
        int minCol = 0;
        
        int curRow = 0;
        int curCol = array[0].size() - 1;
        
        return find_helper(array, target, curRow, curCol, maxRow, minCol); 
    }
		
private:
    bool find_helper(vector<vector<int> > &array, const int target, int &curRow, int &curCol, const int maxRow, const int minCol) {
        if (curRow > maxRow || curCol < minCol) {
            return false;
        }
        
        if (array[curRow][curCol] == target){
            return true;
        } else if (array[curRow][curCol] < target) {
            return find_helper(array, target, ++curRow, curCol, maxRow, minCol);
        } else {
            return find_helper(array, target, curRow, --curCol, maxRow, minCol);
        }
    }
    
};

(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢

最近更新