二维数组中的查找 二维数组中的查找

发表于

「这是我参与11月更文挑战的第26天，活动详情查看：2021最后一次更文挑战」

二维数组中的查找​​

面试题3：

image-20210910134358545

似题:

我做过这个类似的有杨氏矩阵为背景的，实际上是一样的

暴力遍历

二维数组暴力遍历的话时间复杂度为O(n^2^)

虽然暴力但是应付学校考试这个就是一把好手

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
c复制代码#include<stdio.h>
//const 就是因为二维数组是定死的
int search(const int arr[4][4], int num,unsigned int* prow,unsigned int* pcol)
{
	int i = 0;
	//扫描行
	for (i = 0; i < *prow; i++)
	{
		//扫描列
		int j = 0;
		for (j = 0; j < *pcol; j++)
		{
			//与所查数比较判断，有一样的就直接返回
			if (arr[i][j] == num)
			{
				*prow = i;//把坐标传回去
				*pcol = j;
				return 1;//一次返回，之后就不看了，因为已经证明到有这个数了，没必要在做无用功了
			}
		}
	}
	return 0;
}
int main()
{
	int arr[4][4] = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} };
	int num = 0;
	while (1)
	{
		unsigned int row = sizeof(arr) / sizeof(arr[0]);
		unsigned int col = sizeof(arr[0]) / sizeof(arr[0][0]);   //把row，col拉进来就是为了每次再来是更新一次
		//长宽，因为下面我们就是用row，col变量没有用其他变量
		printf("请输入你想要找的数:>");
		scanf("%d", &num);
		if (search(arr, num, &row, &col))//把长宽传地址过去用指针prow，pcol接收
		{
			printf("有这个数\n");
			printf("坐标为(%d,%d)\n", row, col);
		}
		else
		{
			printf("没有这个数\n");
		}
	}	
	return 0;
}

image-20210910163325915

动态基点操作

暴力操作肯定拿不下面试官的心，没有思想，应该优化程序，减小时间复杂度

image-20210910165659391

image-20210910170432274

image-20210910170800065

然后把上面search函数改改就可以了

时间复杂度也降为O(n)

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
c复制代码#include<stdio.h>
//const 就是因为二维数组是定死的
int search(const int arr[4][4], int num,unsigned int* prow,unsigned int* pcol)
{
	int i = 0;
	unsigned int x = 0;
	unsigned int y = *pcol-1;
	while ((x<*prow)&&(y>=0))
	{
		if (arr[x][y] - num > 0)
		{
			y--;
		}
		else if (arr[x][y] - num < 0)
		{
			x++;
		}
		else
		{
			*prow = x;
			*pcol = y;
			return 1;
		}
	}
	return 0;
}
int main()
{
	int arr[4][4] = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} };
	int num = 0;
	while (1)
	{
		unsigned int row = sizeof(arr) / sizeof(arr[0]);
		unsigned int col = sizeof(arr[0]) / sizeof(arr[0][0]);   //把row，col拉进来就是为了每次再来是更新一次
		//长宽，因为下面我们就是用row，col变量没有用其他变量
		printf("请输入你想要找的数:>");
		scanf("%d", &num);
		if (search(arr, num, &row, &col))//把长宽传地址过去用指针prow，pcol接收
		{
			printf("有这个数\n");
			printf("坐标为(%d,%d)\n", row, col);
		}
		else
		{
			printf("没有这个数\n");
		}
	}	
	return 0;
}

image-20210910172040278

结果也是不错的

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%