C語言楊氏矩陣查找算法實例講解

更新時間：2022年09月22日 08:41:46 作者：碳基肥宅

楊氏矩陣是一個數(shù)字矩陣，矩陣的每一行從左到右一次遞增，矩陣從上到下遞增，在這樣的矩陣中查找一個數(shù)字是否存在。時間復(fù)雜度小于O(N)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步早日升職加薪

一、楊氏矩陣介紹

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

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

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

二、查找算法

1.查找思路

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

因為這兩個位置的大于小于有區(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("請輸入你要找的數(shù)：\n");
	while(~scanf("%d", &k)){
		if (Check(a, ROW, COL, k)) {
			printf("找到了！\n");
		}
		else {
			printf("該數(shù)不存在！\n");
		}
	}
	return 0;
}

三、楊氏矩陣例題

傳送門

代碼

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

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

特別注意

針對這串代碼，這里必須附上特別說明。傳二維數(shù)組入函數(shù)，函數(shù)頭寫了形參為int** array，注意這并不是直接傳二維數(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)的元素是指針類型，存放的是另外四個一維數(shù)組名
	printf("%d",Find(100, p,arrayRowLen ,&arrayColLen));
	return 0;
}