C語言編程題楊氏矩陣算法快速上手示例詳解

Posted on by

題目概要

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

一、解題思路

對於查找一個數組中元素是否存在，很多同學第一想法就是從頭到尾遍歷一遍。這樣的想法優點是代碼簡單且無腦容易上手，但是這樣的缺點也很明顯，比如是m *n的數組，你從頭到尾遍歷，最壞情況要找m *n次。題目給的相關條件比如從左向右遞增，從上向下遞增你也完全沒有使用，這樣的暴力求解顯然不是我們想看到的

我們來介紹一種方法，以下列二維數組進行舉例
1 2 3
4 5 6
7 8 9
根據矩陣的每行從左到右都是遞增這個特性，我們知道矩陣的每一行最後一個數都是該行最大的，比如上面這個矩陣的3，6，9。對於7是否在這個矩陣中，我們可以與每行的最後一個數比較，如果7小於當前行，則在當前行遍歷，否則進行與下一行最後一個數的比較，如果最後一行都小於7說明7是不在該矩陣中的

二、具體代碼

代碼如下（示例）：

#include<stdio.h>
void find(int arr[3][3], int k,int h,int l)//h和l分別表示行和列
{
	int x = 0;//第一行橫坐標
	int y = l - 1;//第一行最後一列縱坐標
	for (x = 0,y = l - 1;arr[x][y] < k&&x<=h-1;x++)//判斷條件多加一個x<h-1是防止越數組訪問
	{
		;//過濾掉無用的行
	}
	if (x == h)//x==h說明所有行都不匹配
	{
		printf("該數組沒有這個數\n");
	}
	else if(arr[x][y]>k)
	{
		int i = 0;
		for (i = 0;i < l;i++)
		{
			if (k == arr[x][i])
			{
				printf("找到瞭，該數在第%d行，第%d列", x+1, i + 1);
			}
		}
	}
	else if (arr[x][y] == k)
	{
		printf("找到瞭，該數在第%d行，第%d列", x + 1, y + 1);
	}
}
int main()
{
	int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
	int k = 0;
	printf("請問你要查找的數是：");
	scanf("%d", &k);
	find(arr, k, 3, 3);
}

以上就是C語言編程題楊氏矩陣算法快速上手示例詳解的詳細內容，更多關於C語言編程楊氏矩陣算法的資料請關註WalkonNet其它相關文章！

推薦閱讀：