C語(yǔ)言如何實(shí)現(xiàn)楊氏矩陣

本篇內(nèi)容主要講解“C語(yǔ)言如何實(shí)現(xiàn)楊氏矩陣”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“C語(yǔ)言如何實(shí)現(xiàn)楊氏矩陣”吧!

題目如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

實(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;
}

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

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

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

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

到此，相信大家對(duì)“C語(yǔ)言如何實(shí)現(xiàn)楊氏矩陣”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！