剑指offer04

剑指offer04：二维数组元素查找

题目描述

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

示例:
现有矩阵 matrix 如下：
[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。
给定 target = 20，返回 false。

限制：
0 <= n <= 1000
0 <= m <= 1000

解法一：暴力法

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        for (int i = 0; i<int(matrix.size()); i++)  
        //matrix.size()就是”二维数组”的行数
        {
            for (int j = 0; j<int(matrix[0].size()); j++)  
            //matrix[0].size()就是”二维数组”的列数
            {
                if (matrix[i][j] == target)
                {
                    cout << "The target is in the 2DArray!" << endl;
                    return true;
                }
            }
        }
        cout << "The target is not in the 2DArray!" << endl;
        return false;
    }
};

解法二：找规律

       我们从左下角开始遍历，当该值小于target值时，向右搜索；大于target值时，向上搜索。如果找到target则返回True，否则返回 False。

/******************************************************************
我们从左下角开始遍历，当该值小于 target 值时，向右搜索；
大于 target 值时，向上搜索。如果找到 target 则返回 True，否则返回 False。
******************************************************************/
class Solution2 {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target)
    {
        if (matrix.size() == 0)
            return false;
        int m = matrix.size();
        int n = matrix[0].size();
        int row = m - 1;
        int col = 0;
        while (row>=0&&col<n)
        {
            if (matrix[row][col] < target)
            {
                col++;
            }
            else if (matrix[row][col] > target) {
                row--;
            }
            else
            {
                cout << "The target is in the 2DArray!" << endl;
                return true;
            }

        }
        cout << "The target is not in the 2DArray!" << endl;
        return false;
    }

};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int N = 5, M = 5;
    vector<vector<int> > obj(N,vector<int> (M)); //定义二维动态数组5行5列;


    cout << "请输入二维数组: " << endl;
    for (int i = 0; i < int(obj.size()); i++)
    {
        for (int j = 0; j < int(obj[0].size()); j++)
        {
            cin >> obj[i][j];
        }
        cout << "\n";
    }


    int target;
    cout << "请输入target: " << endl;
    cin >> target;
    //cout << "The target is: " << target << endl;
    Solution2 answer;
    answer.findNumberIn2DArray(obj, target);


    system("pause");
    return 0;
}