本文以C語言實(shí)現(xiàn)，介紹楊氏矩陣中通用的查找算法。

一、楊氏矩陣介紹

楊氏矩陣種，每一行的數(shù)都從左到右遞增，每一列的數(shù)都從上到下遞增。如下圖是一個(gè)簡單的楊氏矩陣：

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

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

二、查找算法

1.查找思路

楊氏矩陣是很有特點(diǎn)的，它有規(guī)律遞增的特點(diǎn)決定了針對(duì)表中的任一元素，它的下方和右方的數(shù)一定大于我，左方和上方的數(shù)一定小于我，所以查找的時(shí)候可利用這一特點(diǎn)，從右上角或者左下角來找。

因?yàn)檫@兩個(gè)位置的大于小于有區(qū)分度。例如，若選擇從右上角找，那么沒有上邊和右邊，而下邊一定比我大，左邊一定比我小。那么，如果要查找的數(shù)比遍歷到的元素大，那我就向下查找；如果比遍歷到的元素小，那我就向左查找。

這樣查找的次數(shù)只有x+y-1次，符合題目中要求的O(n)。

2.步驟

3.代碼

int Check(int a[ROW][COL],int row,int col,int k) {
	int x = 0;
	int y = col - 1;
	while(x <= row-1 && y >= 0){
		if (k > a[x][y]) {    //比我大就向下
			x++;
		}
		else if (k < a[x][y]) {    //比我小就向左
			y--;
		}
		else {
			return 1;    //相等：找到了
		}
	}
	return 0;    //沒有找到
}
int main() {
	int a[ROW][COL] = { {1,2,3,4},{5,6,7,8},{9,10,11,12}};//示例
	int k = 0;    //要查找的數(shù)
	printf("請(qǐng)輸入你要找的數(shù)：\n");
	while(~scanf("%d", &k)){
		if (Check(a, ROW, COL, k)) {
			printf("找到了！\n");
		}
		else {
			printf("該數(shù)不存在！\n");
		}
	}
	return 0;
}

三、楊氏矩陣?yán)}

傳送門

代碼

該題相當(dāng)于是前面楊氏矩陣查找的直接運(yùn)用。注意，當(dāng)題干中出現(xiàn) “一個(gè)二維數(shù)組array中（每個(gè)一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序” 這樣的描述時(shí)，要立馬反應(yīng)過來它是楊氏矩陣?？赡懿粫?huì)每道題的矩陣都像{{1，2，3，4}，{5，6，7，8}，{9，10，11，12}}這樣規(guī)整，但只要關(guān)注并發(fā)現(xiàn)它的行按一定順序（從左到右或從右到左）遞增，且列也按一定順序（從上到下或從下到上）遞增，那么就可以運(yùn)用楊氏矩陣算法。（有時(shí)候可能題干數(shù)組會(huì)是從右向左遞增，從下向上遞增，剛好和楊氏矩陣反一反，但方法通用。）

bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
	int x = 0;
	int y = *arrayColLen - 1;
	while(x < arrayRowLen && y >= 0){
		if(array[x][y] > target) {
			y--;
		}else if(array[x][y] < target) {
			x++;
		}else{
			return true;
		}
	}
	return false;
}

特別注意

針對(duì)這串代碼，這里必須附上特別說明。傳二維數(shù)組入函數(shù)，函數(shù)頭寫了形參為int** array，注意這并不是直接傳二維數(shù)組名時(shí)的形參接收方式。

若實(shí)參部分直接傳二維數(shù)組數(shù)組名array，則形參應(yīng)寫為：

//列參數(shù)不可省略
void fun(int array[][col]);

或

//一維數(shù)組指針
void fun(int (*array)[col]);

而用int** array接收，則調(diào)用方應(yīng)該這樣寫：

#include<stdio.h>
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
	int x = 0;
	int y = *arrayColLen - 1;
	while(x < arrayRowLen && y >= 0){
		if(array[x][y] > target) {
			y--;
		}else if(array[x][y] < target) {
			x++;
		}else{
			return true;
		}
	}
	return false;
}
int main(){
	int a1[]={1,2,8,9};
	int a2[]={2,4,9,12};
	int a3[]={4,7,10,13};
	int a4[]={6,8,11,15};
	int* p[] = {a1,a2,a3,a4};
	int arrayRowLen = 4;
	int arrayColLen = 4;
    //傳入指針數(shù)組的數(shù)組名，數(shù)組p內(nèi)的元素是指針類型，存放的是另外四個(gè)一維數(shù)組名
	printf("%d",Find(100, p,arrayRowLen ,&arrayColLen));
	return 0;
}

四、總結(jié)

概括來說，楊氏矩陣查找的算法是根據(jù)楊氏矩陣中數(shù)遞增規(guī)律特點(diǎn)設(shè)計(jì)的，而這種設(shè)計(jì)算法的思路可以遷移。若題干變換為其它類型的、其中數(shù)具有變化規(guī)律的矩陣，要能想起楊氏矩陣的查找算法，并嘗試將這種設(shè)計(jì)的思路遷移到變式中去。

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

最新評(píng)論