一、题目描述

二、解题思路

可以通过四个顶点，将矩阵分为四个区域

• 左上角：只有比左上角的元素大的，如果从左上角出发，则找不到比较的反馈
• 左下角：右面的同行元素都比它大，上面同列元素都比它小，可以界定寻找路径
• 右上角：同左下角
• 右下角：同左上角

三、解题代码

LeetCode解题代码

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

剑指Offer解题代码

/******************************************************************* Copyright(c) 2016, Harry He All rights reserved. Distributed under the BSD license. (See accompanying file LICENSE.txt at https://github.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt) *******************************************************************/

//==================================================================
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 作者：何海涛
//==================================================================

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

#include <cstdio>
/* bool Find(int* matrix, int rows, int columns, int number) { bool found = false; if(matrix != nullptr && rows > 0 && columns > 0) { int row = 0; int column = columns - 1; while(row < rows && column >=0) { if(matrix[row * columns + column] == number) { found = true; break; } else if(matrix[row * columns + column] > number) -- column; else ++ row; } } return found; } */
bool Find(int *matrix, int rows, int columns, int number)
{
   
    int row = rows - 1, col = 0;
    for (; row >= 0 && col < columns;)
        if (number == matrix[row * columns + col])
            return true;
        else if (number < matrix[row * columns + col])
            row--;
        else
            col++;
    return false;
}

// ====================测试代码====================
void Test(char *testName, int *matrix, int rows, int columns, int number, bool expected)
{
   
    if (testName != nullptr)
        printf("%s begins: ", testName);

    bool result = Find(matrix, rows, columns, number);
    if (result == expected)
        printf("Passed.\n");
    else
        printf("Failed.\n");
}

// 1 2 8 9
// 2 4 9 12
// 4 7 10 13
// 6 8 11 15
// 要查找的数在数组中
void Test1()
{
   
    int matrix[][4] = {
   {
   1, 2, 8, 9}, {
   2, 4, 9, 12}, {
   4, 7, 10, 13}, {
   6, 8, 11, 15}};
    Test("Test1", (int *)matrix, 4, 4, 7, true);
}

// 1 2 8 9
// 2 4 9 12
// 4 7 10 13
// 6 8 11 15
// 要查找的数不在数组中
void Test2()
{
   
    int matrix[][4] = {
   {
   1, 2, 8, 9}, {
   2, 4, 9, 12}, {
   4, 7, 10, 13}, {
   6, 8, 11, 15}};
    Test("Test2", (int *)matrix, 4, 4, 5, false);
}

// 1 2 8 9
// 2 4 9 12
// 4 7 10 13
// 6 8 11 15
// 要查找的数是数组中最小的数字
void Test3()
{
   
    int matrix[][4] = {
   {
   1, 2, 8, 9}, {
   2, 4, 9, 12}, {
   4, 7, 10, 13}, {
   6, 8, 11, 15}};
    Test("Test3", (int *)matrix, 4, 4, 1, true);
}

// 1 2 8 9
// 2 4 9 12
// 4 7 10 13
// 6 8 11 15
// 要查找的数是数组中最大的数字
void Test4()
{
   
    int matrix[][4] = {
   {
   1, 2, 8, 9}, {
   2, 4, 9, 12}, {
   4, 7, 10, 13}, {
   6, 8, 11, 15}};
    Test("Test4", (int *)matrix, 4, 4, 15, true);
}

// 1 2 8 9
// 2 4 9 12
// 4 7 10 13
// 6 8 11 15
// 要查找的数比数组中最小的数字还小
void Test5()
{
   
    int matrix[][4] = {
   {
   1, 2, 8, 9}, {
   2, 4, 9, 12}, {
   4, 7, 10, 13}, {
   6, 8, 11, 15}};
    Test("Test5", (int *)matrix, 4, 4, 0, false);
}

// 1 2 8 9
// 2 4 9 12
// 4 7 10 13
// 6 8 11 15
// 要查找的数比数组中最大的数字还大
void Test6()
{
   
    int matrix[][4] = {
   {
   1, 2, 8, 9}, {
   2, 4, 9, 12}, {
   4, 7, 10, 13}, {
   6, 8, 11, 15}};
    Test("Test6", (int *)matrix, 4, 4, 16, false);
}

// 鲁棒性测试，输入空指针
void Test7()
{
   
    Test("Test7", nullptr, 0, 0, 16, false);
}

int main(int argc, char *argv[])
{
   
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    Test7();

    return 0;
}

四、运行结果

LeetCode运行结果

剑指Offer测试结果

FindInPartiallySortedMatrix.cpp: In function 'void Test1()':
FindInPartiallySortedMatrix.cpp:81:47: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
     Test("Test1", (int *)matrix, 4, 4, 7, true);
                                               ^
FindInPartiallySortedMatrix.cpp: In function 'void Test2()':
FindInPartiallySortedMatrix.cpp:92:48: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
     Test("Test2", (int *)matrix, 4, 4, 5, false);
                                                ^
FindInPartiallySortedMatrix.cpp: In function 'void Test3()':
FindInPartiallySortedMatrix.cpp:103:47: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
     Test("Test3", (int *)matrix, 4, 4, 1, true);
                                               ^
FindInPartiallySortedMatrix.cpp: In function 'void Test4()':
FindInPartiallySortedMatrix.cpp:114:48: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
     Test("Test4", (int *)matrix, 4, 4, 15, true);
                                                ^
FindInPartiallySortedMatrix.cpp: In function 'void Test5()':
FindInPartiallySortedMatrix.cpp:125:48: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
     Test("Test5", (int *)matrix, 4, 4, 0, false);
                                                ^
FindInPartiallySortedMatrix.cpp: In function 'void Test6()':
FindInPartiallySortedMatrix.cpp:136:49: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
     Test("Test6", (int *)matrix, 4, 4, 16, false);
                                                 ^
FindInPartiallySortedMatrix.cpp: In function 'void Test7()':
FindInPartiallySortedMatrix.cpp:142:43: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
     Test("Test7", nullptr, 0, 0, 16, false);
                                           ^
Test1 begins: Passed.
Test2 begins: Passed.
Test3 begins: Passed.
Test4 begins: Passed.
Test5 begins: Passed.
Test6 begins: Passed.
Test7 begins: Passed.