日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

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

作者：碳基肥宅 ? 更新時間： 2022-11-12 編程語言

本文以C語言實現，介紹楊氏矩陣中通用的查找算法。

一、楊氏矩陣介紹

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

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

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

二、查找算法

1.查找思路

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

因為這兩個位置的大于小于有區分度。例如，若選擇從右上角找，那么沒有上邊和右邊，而下邊一定比我大，左邊一定比我小。那么，如果要查找的數比遍歷到的元素大，那我就向下查找；如果比遍歷到的元素小，那我就向左查找。

這樣查找的次數只有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;    //要查找的數
	printf("請輸入你要找的數：\n");
	while(~scanf("%d", &k)){
		if (Check(a, ROW, COL, k)) {
			printf("找到了！\n");
		}
		else {
			printf("該數不存在！\n");
		}
	}
	return 0;
}

三、楊氏矩陣例題

傳送門

代碼

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

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** array，注意這并不是直接傳二維數組名時的形參接收方式。

若實參部分直接傳二維數組數組名array，則形參應寫為：

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

或

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

而用int** array接收，則調用方應該這樣寫：

#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;
    //傳入指針數組的數組名，數組p內的元素是指針類型，存放的是另外四個一維數組名
	printf("%d",Find(100, p,arrayRowLen ,&arrayColLen));
	return 0;
}

四、總結

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

原文鏈接：https://blog.csdn.net/wyd_333/article/details/126575604

欄目分類
最近更新