C语言杨氏矩阵查找算法实例讲解

目录
  • 一、杨氏矩阵介绍
  • 二、查找算法
    • 1.查找思路
    • 2.步骤
    • 3.代码
  • 三、杨氏矩阵例题
    • 代码
    • 特别注意
  • 四、总结

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

四、总结

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

到此这篇关于C语言杨氏矩阵查找算法实例讲解的文章就介绍到这了,更多相关C语言杨氏矩阵内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言编程题杨氏矩阵算法快速上手示例详解

    目录 题目概要 一.解题思路 二.具体代码 题目概要 有一个数字矩阵,矩阵的每行从左到右都是递增的,矩阵从上到下都是递增的,请编写程序在这样的矩阵中查找某个数字是否存在? 一.解题思路 对于查找一个数组中元素是否存在,很多同学第一想法就是从头到尾遍历一遍.这样的想法优点是代码简单且无脑容易上手,但是这样的缺点也很明显,比如是m *n的数组,你从头到尾遍历,最坏情况要找m *n次.题目给的相关条件比如从左向右递增,从上向下递增你也完全没有使用,这样的暴力求解显然不是我们想看到的 我们来介绍一种方法

  • C语言中杨氏矩阵与杨辉三角的实现方法

    一.杨氏矩阵 杨氏矩阵 1.杨氏矩阵的概念 在数学中,杨表(英语:Young tableau),又称杨氏矩阵.是对组合表示理论和舒伯特演算很有用的工具.它提供了一种方便的方式来描述对称和一般线性群的群表示,并研究它们的性质.杨表是剑桥大学数学家 Alfred Young 在1900年推提出.然后,它被弗罗贝尼乌斯应用对称群的研究中.他们的理论由许多数学家进一步发展,包括PercyMacMahon.W. V. D. Hodge.G. de B. Robinson.吉安-卡洛·罗塔.Alain La

  • C语言杨氏矩阵查找算法实例讲解

    目录 一.杨氏矩阵介绍 二.查找算法 1.查找思路 2.步骤 3.代码 三.杨氏矩阵例题 代码 特别注意 四.总结 本文以C语言实现,介绍杨氏矩阵中通用的查找算法. 一.杨氏矩阵介绍 杨氏矩阵种,每一行的数都从左到右递增,每一列的数都从上到下递增.如下图是一个简单的杨氏矩阵: 有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在. 要求:时间复杂度小于O(N) 二.查找算法 1.查找思路 杨氏矩阵是很有特点的,它有规律递增的特点决定了针对

  • C语言杨氏矩阵实例教你编写

    目录 一.杨氏矩阵是什么 二.编写步骤 三.程序的改进 四.总结 一.杨氏矩阵是什么 一个数字矩阵,矩阵的每一行从左到右一次递增,矩阵从上到下递增,在这样的矩阵中查找一个数字是否存在.时间复杂度小于O(N). 二.编写步骤 1.首先给出一个三乘三的矩阵,我们想找到数字7是否在这个数组之中,如图所示. 2. 我们给出的方法是一种从右上角开始,另一种是从左下角开始.比如从右上角开始,编写一个函数. 3. 函数的编写.从右上角开始,将右上角数字与数字7比较,如果数字7大于右上角的数字(3)(因为第一行

  • Python 语言实现六大查找算法

    目录 一.顺序查找算法 二.折半查找算法 三.插补查找算法 四.哈希查找算法 五.分块查找算法 六.斐波那契查找算法 七.六种查找算法的时间复杂度 一.顺序查找算法 顺序查找又称为线性查找,是最简单的查找算法.这种算法就是按照数据的顺序一项一项逐个查找,所以不管数据顺序如何,都得从头到尾地遍历一次.顺序查找的优点就是数据在查找前,不需要对其进行任何处理(包括排序).缺点是查找速度慢,如果数据列的第一个数据就是想要查找的数据,则该算法查找速度为最快,只需查找一次即可:如果查找的数据是数据列的最后一

  • python实现杨氏矩阵查找

    本文实例为大家分享了python实现杨氏矩阵查找的具体代码,供大家参考,具体内容如下 问题描述: 在一个m行n列二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数.有则返回1,无则返回0,输入错误返回input error 问题分析:根据杨氏矩阵的规律可知,左上角是最小元素,右下角是最大元素,进行比较一次只能排除一个.而利用左下角或者右上角对比,一次可以排除一行或一列. AC代码以右上角为

  • R语言基础统计方法图文实例讲解

    tidyr > tdata <- data.frame(names=rownames(tdata),tdata)行名作为第一列 > gather(tdata,key="Key",value="Value",cyl:disp,mpg)创key列和value列,cyl和disp放在一列中 -号减去不需要转换的列 > spread(gdata,key="Key",value="Value") 根据value将

  • 杨氏矩阵查找的JS代码

    复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="

  • JS数组操作中的经典算法实例讲解

    冒泡排序 <script type="text/javascript"> var arr = [3,7,6,2,1,5]; 定义一个交换使用的中间变量 var temp = 0; for(i=0;i<arr.length;i++){ for(j=0;j<arr.length;j++){ 如果下一个元素小于当前元素 if(arr[j]>arr[j+1]){ 互换 temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tem

  • SPFA 算法实例讲解

    适用范围:给定的图存在负权边,这时类似Dijkstra等算法便没有了用武之地,而Bellman-Ford算法的复杂度又过高,SPFA算法便 派上用场了. 我们约定有向加权图G不存在负权回路,即最短路径一定存在.当然,我们可以在执行该算法前做一次拓扑排序,以判断是否存在负权回路,但这不是我们讨论的重 点. 算法思想:我们用数组d记录每个结点的最短路径估计值,用邻接表来存储图G.我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的 结点,优化时每次取出队首结点u,并且用u点当前的最短路

  • NetworkX之Prim算法(实例讲解)

    引言 Prim算法与Dijkstra的最短路径算法类似,它采用贪心策略.算法开始先把图中权值最小的边添加到树T中,然后不断把权值最小的边E(E的一个端点在T中,另一个在G-T中).当没有符合条件的E时算法结束,此时T就是G的一个最小生成树. NetworkX是一款Python的软件包,用于创造.操作复杂网络,以及学习复杂网络的结构.动力学及其功能. 本文借助networkx.Graph类实现Prim算法. 正文 Prim算法的代码 Prim def prim(G, s): dist = {} #

  • python增加矩阵维度的实例讲解

    numpy.expand_dims(a, axis) Examples >>> x = np.array([1,2]) >>> x.shape (2,) >>> y = np.expand_dims(x, axis=0) >>> y array([[1, 2]]) >>> y.shape (1, 2) >>> y = np.expand_dims(x, axis=1) # Equivalent to

随机推荐