今天來(lái)向大家介紹一個(gè)用C語(yǔ)言實(shí)現(xiàn)楊氏矩陣的問(wèn)題。題目如下：

有一個(gè)數(shù)字矩陣，矩陣的每行從左到右是遞增的，矩陣從上到下是遞增的，請(qǐng)編寫(xiě)程序在這樣的矩陣中查找某個(gè)數(shù)字是否存在。

要求：時(shí)間復(fù)雜度小于O(N);

題干中所描述的矩陣被稱(chēng)作楊氏矩陣，然后讓你在這個(gè)這個(gè)矩陣中查找一個(gè)數(shù)字。其實(shí)在矩陣中查找一個(gè)數(shù)字并不難，只需采取遍歷的方式，將矩陣中每個(gè)元素拿出來(lái)比較即可。但這道題還有一個(gè)要求就是時(shí)間復(fù)雜度必須小于O（N）,也就是說(shuō)不能采用遍歷的方式來(lái)查找。因此我們需要根據(jù)楊氏矩陣的特點(diǎn)來(lái)寫(xiě)一個(gè)新的算法進(jìn)行查找。

如下圖所示，為一個(gè)3x3的楊氏矩陣。

根據(jù)題目我們總結(jié)一下楊氏矩陣的兩個(gè)特點(diǎn)：

1. 同一行的元素由左向右依次遞增

2. 同一列的元素從上到下依次遞增

通過(guò)這兩點(diǎn)我們會(huì)發(fā)現(xiàn)這個(gè)矩陣有兩個(gè)元素是特殊元素。

• 右上角元素3為其所在行最大的元素，為其所在列最小的元素
• 左下角元素7為其所在行最小的元素，為其所在列最大的元素

因此我們可以采用以下方法：

先拿出右上角的元素3來(lái)和所查找的元素比較，如果3比要查找的元素大，那說(shuō)明該元素絕不可能在第一行，因此我們就可以直接排除一行的元素。如果3比要查找的元素小，那說(shuō)明該元素絕不可能在最后一列，因此我們就可以直接排除一列的元素

現(xiàn)在假設(shè)我們排除了一行的元素，那接下來(lái)的矩陣就變成了這樣：

這時(shí)6又變成了右上角的元素，然后重復(fù)上一步的操作，假設(shè)我們這次排除了一列的元素，那接下來(lái)的矩陣就變成了這樣：

于是5變成了右上角的元素，繼續(xù)重復(fù)上一步操作，這樣每一次查找我們都可以排除一行或者一列的元素，大大的提高了算法效率。

當(dāng)然上述舉例我是以右上角元素為基準(zhǔn)的，如果以左下角元素為基準(zhǔn)也可以得到相同的結(jié)果，大家不妨自己來(lái)試一下。

實(shí)現(xiàn)代碼如下：

#include <stdio.h>
int find_num(int arr[3][3], int row, int col, int k)
{
	int x = 0;
	int y = col-1;
	while (x<row && y>=0)
	{
		if (arr[x][y] == k)
		{
			printf("下標(biāo)為： %d %d\n", x, y);
			return 1;
		}
		else if (arr[x][y] > k)
			y--;
		else if (arr[x][y] < k)
			x++;
	}
	return 0;
}
int main()
{
	int arr[3][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	int ret = find_num(arr, 3, 3, 7);
	if (ret == 1)
		printf("找到了\n");
	else
		printf("找不到\n");
	return 0;
}

這里我們將查找楊氏矩陣元素的過(guò)程封裝在一個(gè)函數(shù)中。函數(shù)接收4個(gè)參數(shù)，分別是二維數(shù)組的地址，行數(shù)，列數(shù)和要查找的元素。通過(guò)返回值來(lái)判斷是否找到。

在函數(shù)內(nèi)部定義一個(gè)坐標(biāo)（x, y）表示右上角元素，當(dāng)x等于行數(shù)是說(shuō)明已經(jīng)越界(數(shù)組下標(biāo)是從0開(kāi)始的)，那要查找的元素必然不存在。當(dāng)列數(shù)小于0也一樣。

當(dāng)排除一行的時(shí)候，給x的值加1即可；排除一列的時(shí)候，給y的值減1即可。

運(yùn)行結(jié)果：

到此這篇關(guān)于C語(yǔ)言楊氏矩陣簡(jiǎn)單實(shí)現(xiàn)方法的文章就介紹到這了,更多相關(guān)C語(yǔ)言楊氏矩陣內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論