C語言如何實現楊氏矩陣

本篇內容主要講解“C語言如何實現楊氏矩陣”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“C語言如何實現楊氏矩陣”吧!

題目如下：

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

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

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

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

根據題目我們總結一下楊氏矩陣的兩個特點：

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

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

通過這兩點我們會發現這個矩陣有兩個元素是特殊元素。

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

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

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

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

現在假設我們排除了一行的元素，那接下來的矩陣就變成了這樣：

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

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

當然上述舉例我是以右上角元素為基準的，如果以左下角元素為基準也可以得到相同的結果，大家不妨自己來試一下。

實現代碼如下：

#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("下標為： %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;
}

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

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

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

運行結果：

到此，相信大家對“C語言如何實現楊氏矩陣”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！