二維數(shù)組中的查找

面試題3：

似題:

我做過(guò)這個(gè)類似的有楊氏矩陣為背景的，實(shí)際上是一樣的

暴力遍歷

二維數(shù)組暴力遍歷的話時(shí)間復(fù)雜度為O(n2)

雖然暴力但是應(yīng)付學(xué)校考試這個(gè)就是一把好手

#include<stdio.h>
//const 就是因?yàn)槎S數(shù)組是定死的
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++)
		{
			//與所查數(shù)比較判斷，有一樣的就直接返回
			if (arr[i][j] == num)
			{
				*prow = i;//把坐標(biāo)傳回去
				*pcol = j;
				return 1;//一次返回，之后就不看了，因?yàn)橐呀?jīng)證明到有這個(gè)數(shù)了，沒(méi)必要在做無(wú)用功了
			}
		}
	}
	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拉進(jìn)來(lái)就是為了每次再來(lái)是更新一次
		//長(zhǎng)寬，因?yàn)橄旅嫖覀兙褪怯胷ow，col變量沒(méi)有用其他變量
		printf("請(qǐng)輸入你想要找的數(shù):>");
		scanf("%d", &num);
		if (search(arr, num, &row, &col))//把長(zhǎng)寬傳地址過(guò)去用指針prow，pcol接收
		{
			printf("有這個(gè)數(shù)\n");
			printf("坐標(biāo)為(%d,%d)\n", row, col);
		}
		else
		{
			printf("沒(méi)有這個(gè)數(shù)\n");
		}
	}	
	return 0;
}

動(dòng)態(tài)基點(diǎn)操作

暴力操作肯定拿不下面試官的心，沒(méi)有思想，應(yīng)該優(yōu)化程序，減小時(shí)間復(fù)雜度

然后把上面search函數(shù)改改就可以了

時(shí)間復(fù)雜度也降為O(n)

#include<stdio.h>
//const 就是因?yàn)槎S數(shù)組是定死的
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拉進(jìn)來(lái)就是為了每次再來(lái)是更新一次
		//長(zhǎng)寬，因?yàn)橄旅嫖覀兙褪怯胷ow，col變量沒(méi)有用其他變量
		printf("請(qǐng)輸入你想要找的數(shù):>");
		scanf("%d", &num);
		if (search(arr, num, &row, &col))//把長(zhǎng)寬傳地址過(guò)去用指針prow，pcol接收
		{
			printf("有這個(gè)數(shù)\n");
			printf("坐標(biāo)為(%d,%d)\n", row, col);
		}
		else
		{
			printf("沒(méi)有這個(gè)數(shù)\n");
		}
	}	
	return 0;
}

結(jié)果也是不錯(cuò)的

以上就是C語(yǔ)言面試C++二維數(shù)組中的查找示例的詳細(xì)內(nèi)容，更多關(guān)于C++二維數(shù)組中的查找的資料請(qǐng)關(guān)注服務(wù)器之家其它相關(guān)文章！

原文鏈接：https://blog.csdn.net/diandengren/article/details/120226553