亲宝软件园·资讯

展开

C语言杨氏矩阵

碳基肥宅 人气:0

本文以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;
}

四、总结

概括来说,杨氏矩阵查找的算法是根据杨氏矩阵中数递增规律特点设计的,而这种设计算法的思路可以迁移。若题干变换为其它类型的、其中数具有变化规律的矩阵,要能想起杨氏矩阵的查找算法,并尝试将这种设计的思路迁移到变式中去。

加载全部内容

相关教程
猜你喜欢
用户评论