C语言杨氏矩阵

叁歲伎倆 2024-03-17 23:33 90阅读 0赞

描述

有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。

要求

时间复杂度小于O(N)。

1.遍历矩阵 时间复杂度O（N）。

int main()
    { 
    	int a[3][4]={ 1,2,3,5,2,4,6,9,4,6,9,13 };
    	int b = 0;
    	printf("请输入要查找的数字：\n");
    	scanf("%d", &b);
    	int x = 0, y = 0;//行 列
    	for ( x = 0; x < 3; x++)
    	{
    		for (y=0; y < 4; y++) 
    		{
    			if (a[x][y] == b)
    			{
    				printf("找到您要查找的数字，其在杨氏矩阵中位于%d行%d列", x+1, y+1);
    				return 0;
    			}
    		}
    	}
    	printf("您要查找的数字不在杨氏矩阵中");
    	return 0;
    }

2. 杨氏矩阵每行从左向右递增，每列从上向下递增。

![c95dbe61ef8d48e9aab6868a8061b260.png][]

分析：矩阵右上角的元素为一行中的最大值，一列中的最小值。当我们以假设为a的右上角元素要查找的数进行比较，若a大于查找的数，而a又是一列中的最小值，则我们所比较的列数进行左移也就是忽略a所在的列；若a小于查找的数，而a又是一行中的最大值，则我们所比较的行数进行下移也就是忽略a所在的行，如此循环直至剩余一个元素，此算法的时间复杂度小于O(N)。

#include<stdio.h>
    int main()
    {
    	int a[3][4]={ 1,2,3,5,2,4,6,9,4,6,9,13 };
    	int b = 0;
    	printf("请输入要查找的数字：\n");
    	scanf("%d", &b);
    	int x = 0, y = 3;//行 列
    	int flog = 0;
    	while (x < 3 && y>0)
    	{
    		if (a[x][y] > b)
    		{
    			y--;
    		}
    		else if (a[x][y] < b)
    		{
    			x++;
    		}
    		else
    		{
    			flog = 1;
    			printf("找到您要查找的数字，其在杨氏矩阵中位于%d行%d列", x+1, y+1);
    			return;
    		}
    	}
    	if (flog == 0)
    		printf("您要查找的数字不在杨氏矩阵中");
    	return 0;
    }

3.因所查找的算法行数多可以自定义函数用指针实现。

//查找的数   行数  列数
    void yangshi_serach(int a[3][4], int b, int* px, int* py)
    {
    	int x = 0;
    	int y = *py - 1;
    	while (x<*px&& y>=0)
    	{
    		if (a[x][y] > b)
    		{
    			y--;
    		}
    		else if (a[x][y]< b)
    		{
    			x++;
    		}
    		else
    		{
    			*px = x;
    			*py = y;
    			return;
    		}
    	}
    	*px = - 1;
    	*py = -1;
    	return;
    }
    int main()
    {
    	int a[3][4] = { 1,2,3,5,2,4,6,9,4,6,9,13 };
    	int b = 0;
    	printf("请输入要查找的数字：\n");
    	scanf("%d", &b);
    	int x = 3, y = 4;//行 列
    	int flog = 0;
    	yangshi_serach(a,b,&x,&y);
    	if (x == -1&&y==-1)
    		printf("您要查找的数字不在杨氏矩阵中");
    	else
    		printf("找到您要查找的数字，其在杨氏矩阵中位于%d行%d列", x + 1, y + 1);
    	return 0;
    }

[c95dbe61ef8d48e9aab6868a8061b260.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/f296a281d00f4750b9f8a332dc227481.png