剑指offer刷题（1）：二维数组中的查找

发表于 | 阅读次数:

剑指offer刷题（1）：二维数组中的查找

刷题平台：牛客网

二维数组中的查找

考点：

数组

1、题目描述

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

2、解题思路

对于一个二维数组，每一行都按照从左到右递增的顺序，每一列都按照从上到下递增的顺序排列，那么我们要想实现在这个数组中查找一个数。我们可以有很多个思路：

  • 1、从第一个数据向后或者最后一个数据向前挨个查找一遍，直至查到该数据或者查完所有数据为止。虽然这种方法可以实现，但是比较麻烦。
  • 2、我们可以利用数组行列都是递增的这么一个关系，因此我们可以从数组的左下角或者右上角开始查找，让所需要查找的数组与左下角或者右上角的数据进行比较，这样我们就可以利用矩阵的特性来不断的缩小数据应该出现的范围，从而可以很快的找出数据，当然也可以很快的确定该数据是否存在与改数组中。

3、算法实现

C实现

为了方便这里的矩阵我并没有手动输入，而是直接放在程序里面的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include "stdio.h"

bool Find(int targe, int *array, int rows, int cols);

bool Find(int targe, int *array, int rows, int cols)
{
	int i = rows - 1, j = 0;
	while (i > 0 && j < cols)
	{
		if (targe < array[cols * i + j]/**((int *)array + cols * i + j)*/  /*array[i][j]*/)
		{
			i--;
		}
		else if (targe>array[cols * i + j] /**((int *)array + cols * i + j)*/  /*array[i][j]*/)
		{
			j++;
		}
		else
		{
			printf("找到了该数，位置为（%d,%d）\t第%d行,第%d列\n",i,j,i+1,j+1);
			return true;
		}
	}
	printf("该数组中没有该数。\n");
	return false;
}

int main()
{
	//先定义一个二维数组
	int a[5][5] = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 }, { 21, 22, 23, 24, 25 } };
	int targe=0;
	int cols = sizeof(a[0]) / sizeof(a[0][0]);
	int rows = sizeof(a) / sizeof(a[0]);
	printf("二维数组为：\n");
	for (int i = 0; i < rows; i++)
	{
		for (int j = 0; j < cols; j++)
		{
			printf("%d\t", a[i][j]);
		}
		printf("\n");
	}
	printf("\n矩阵的大小为：rows=%d\tcols=%d\n", rows, cols);
	printf("请输入需要查询的数字：\n");
	scanf_s("%d", &targe);
	printf("需要查询的数字为：%d\n",targe);

	Find(targe, *a, rows, cols);
}

C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int rows=array.size();
        int cols=array[0].size();
        int i=rows-1,j=0;
        while(i>=0&&j<cols)
        {
            if(target<array[i][j])
            {
                i--;
            }
            else if (target>array[i][j])
            {
                j++;
            }
            else
            {
                return true;
            }
        }
        return false;
    }
};

C语言实现结果