今天來向大家介紹一個用C語言實現(xiàn)楊氏矩陣的問題。題目如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

運行結(jié)果：

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

最新評論