牛客网-剑指Offer 二维数组中的查找

题目描述

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

思路分析：使用蛮力的话数组行列比较多的时候会很耗时。所以还是要想办法来缩小查找范围。

这个数组的定义是从左到右递增，从上到下递增，但是并不是所有在当前数字的右边的都比他大，也不是所有在当前数字下面的都比他大。

举个栗子：

1 2 7 9

2 5 8 15

8 10 13 20

如果随机选取一个数字的话是没有规律的。

1、从左上角来说，如果一个数比他大，只能是往后查找，如果一个数比他小你也不能剔除一列或者一行，右小角同理。

2、所以选择从右上角或者左下角出发来解决这个问题：(array[i][j]代表当前元素)

　　二者原理相同，理解其一即可。

（1）如果是从右上角出发，如果target<array[i][j]的话，是不是说明比他大的元素就不用查找了？当前元素所在的列就可以剔除掉了。

如果target>array[i][j]，是不是说明目标元素比当前元素还要大，因为是右上角，所以他这行左边的元素都比他大，那么当前行元素就可以剔除了。

（2）如果从左下角出发，如果target<array[i][j]，说明目标元素比当前元素还要小就说明比他大的不用再查找了，所以就可以剔除一行元素了。

如果target>array[i][j]，说明目标元素比当前元素要大，那么比他小的就不用再找了，就可以剔除一列。

贴一下代码，是按右上角出发的：

#include<iostream>

#include<vector>

using namespace std;

bool Find(int target, vector<vector<int> > array) {

    bool result = false;

    int row = array.size();

    int column = array[0].size();

    int i = 0, j = column - 1;

    if (!array.empty() && row > 0 && column > 0) {

        //从右上角开始扫描，当前数<target小的就剔除当前行，当前数>target大的就剔除当前列

        while (i < row&&j>=0) {

            if (array[i][j] == target) {

                //找到

                return true;

            }

            else if (array[i][j] > target) {

                j--;

            }

            else {

                i++;

            }

        }

    }

}

巴特西

牛客网-剑指Offer 二维数组中的查找

题目描述

最新文章

热门文章