刷题笔记 | 剑指Offer 03 二维数组中的查找
导言
本文主要讲解《剑指Offer》中第03题"二维数组中的查找"，介绍题目、解决思路、解题步骤，并分别以C++和Python编程语言解答此题。
编辑: Amusi
校稿: Amusi
前戏
Amusi 的编程能力较差，想到也快秋招了，很有必要提升自己的编程能力，开拓自己的解题思路。这个 "刷题笔记" 主题，两个月前就已经萌发了，但因为事情较多，很多东西没有准备好，所以迟迟没有启动。
刷题笔记主要以 LeetCode和 剑指Offer为主，因为两者题量都很大，所以暂时不会再扩展。编程语言主要以 C++和 Python为主。
Amusi 将日常刷题的笔记同步发布到 coding-note 上。喜欢的童鞋，欢迎star、fork和pull。
直接点击“阅读全文”即可访问 coding-note。
https://github.com/amusi/coding-note
温馨提示：文末有 CVer 刷题群 二维码链接，你懂的
03 二维数组中的查找
题目
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路
根据题目信息，可以知道输入和输出信息如下：
- 输入: 二维数组和待查询的整数
- 输出: 待查询整数是否在二维数组(True, False)
已经二维数组是称规律排列，我们可以先确定一个查询起点，再根据已知的排列规律进行查询。如将二维数组左下角元素作为查询起点，比较左下角元素与待查询数值的大小，如果左下角元素小于待查询数值，则根据排列规则，应该将列数+1。再进行比较，直到左下角元素大于待查询数值，此时即可以将行数-1。继续查询，直到左下角元素等于待查询数值，即可返回True，反之，返回False。
解题步骤
二维数组matrix, 二维数组行数: rows，二维数组列数: cols, 待查询数值 num
1.先将二维数组转换成一维数组进行处理
2.定义判断初始值为左下角元素matrix[row][col]，其中row=rows-1, col=0
3.将二维数组的左下角元素matrix[row][col]（或者右上角元素）值与带查询num进行比较，
如果matrix[row][col] > num，则--row；如果matrix[row][col] < num，则++col。
4.重复第3步，直到遍历完所有可以遍历的数组元素。
举个栗子，如下图所示（图虽然有点丑，但应该能看懂，嘻嘻）
C++ & Python 代码
C++代码
版本1：char[][]二维数组
1// 版本1: char[][]二维数组（手动输入示例）
2
3#include <iostream>
4
5// 定义一个 4*4 的二维数组
6const int matrix_cols = 4;
7int matrix[][matrix_cols] = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, {6, 8, 11, 15} };
8
9bool judge_inter_in_array(int search_num, int *matrix, const int matrix_cols, const int matrix_rows);
10
11int main()
12{
13 int search_num = 9;
14
15 // 二维数组转换成一维数组处理
16 const int matrix_eles = sizeof(matrix) / sizeof(matrix[0][0]);
17 const int matrix_rows = matrix_eles / matrix_cols;
18
19 judge_inter_in_array(search_num, (int*)matrix, matrix_cols, matrix_rows);
20
21
22 return 0;
23}
24
25/**********************************
26功能: 判断输入整数是否在数组中
27输入: 待查询数字, 二维数组, 数组的列数, 数组的行数
28输出:
29
30***********************************/
31bool judge_inter_in_array(int search_num, int *matrix, const int matrix_cols, const int matrix_rows)
32{
33
34 bool found = false;
35 int row = matrix_rows - 1;
36 int col = 0;
37
38 if (matrix!=NULL && matrix_cols > 0 && matrix_rows > 0)
39 {
40
41
42 // 限定搜索范围
43 while (col < matrix_cols && row >= 0)
44 {
45 if (matrix[row*matrix_cols + col] == search_num)
46 {
47 found = true;
48 break;
49 }
50 else if (matrix[row*matrix_cols + col] < search_num)
51 ++col;
52 else
53 --row;
54 }
55 }
56
57 if (found == true)
58 {
59 std::cout << "True" << std::endl;
60 // add: 添加元素位置索引的输出语句
61 std::cout << search_num << " 位于 "<< row+1 << " 行，第"<< col+1 <<" 列" <<std::endl;
62 }
63 else
64 std::cout << "False" << std::endl;
65
66 return found;
67}
68版本2：vector二维数组
1// 版本二: vector二维数组（牛客网，系统输入示例）
2
3class Solution {
4public:
5 bool Find(int target, vector<vector<int> > array) {
6 int matrix_rows = array.size(); // 二维数组行数
7 int matrix_cols = array[0].size(); // 二维数组列数
8 int row = matrix_rows - 1;
9 int col = 0;
10 // 判断输入的二维数组是否符合要求
11 if (matrix_rows == 0 && matrix_cols == 0)
12 return false;
13 // 循环
14 while (row >= 0 && col < matrix_cols)
15 { // 比较当前元素和待查询元素大小
16 if (target < array[row][col])
17 {
18 --row; // 减行
19 }
20 else if (target > array[row][col])
21 {
22 ++col; // 加列
23 }
24 else
25 return true;
26 }
27 return false;
28 }
29};Python代码
1def judge_inter_in_array(matrix, rows, cols, search_num):
2 ''' 判断数组中是否含有该整数'''
3 row = rows-1
4 col = 0
5
6 if rows==0 or cols==0:
7 return False
8
9 while rows>=0 and col<cols:
10 if matrix[row][col] > search_num:
11 row = row-1
12 elif matrix[row][col] < search_num:
13 col = col+1
14 else:
15 return True
16
17 return False
18
19if __name__ == '__main__':
20 matrix = [
21 [1, 2, 8, 9],
22 [2, 4, 9, 12],
23 [4, 7, 10, 13],
24 [6, 8, 11, 15]
25 ]
26
27 print(judge_inter_in_array(matrix, 4, 4, 11))