杨氏矩阵

Yui_

发布于 2024-10-15 21:14:01

870

发布于 2024-10-15 21:14:01

文章被收录于专栏：Yui编程知识

呀哈喽，我是结衣。

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

要求：时间复杂度小于O(N);

因为要求有时间复杂度要小于O(N)的条件，我们就尽量用一个循环解决这个问题把。仔细分析题目不难发现右上角的数是矩阵中一行中最大的一个数，同时也是一列中最小的一个数。如图

那么我们要怎么利用这一个性质呢？试想一下如果我们要找的数子比右上角的数要小，那么它不就在右上角的左边了吗，我们就可以把最后一列给去掉了，如果我们要找的数比右上角的数要大，那么它就在右上角的下面，我们就可以把第一行给去掉了，有了这个思路，我们就可以利用循环来实现这个想法了。可能你也会向左下角可不可以，它具有和右上角差不多的性质，那么你觉得它可不可以呢？思路完成了，我们就可以敲代码咯

#include <stdio.h>
int findnum(int arr[][5], int x, int y, int f)
{
	int i = 0; int j = y - 1;//找到右上角的数
	while (j >= 0 && i < x)
	{
		if (arr[i][j] < f)
		{
			i++;
		}
		else if(arr[i][j]>f)
		{
			j--;
		}
		else
		{
			return 1;
		}
	}
	return 0;
}
int main()
{
      int arr[][5] = { {1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7} };
	  if (findnum(arr, 3, 5, 2))
	  {
		  printf("It has been found!\n");
	  }
	  else
	  {
		  printf("It hasn't been found!\n");
	  }

	return 0;
}

完

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-15，如有侵权请联系 cloudcommunity@tencent.com 删除

int