关于建设网站的申请报告,wordpress选项下拉,那个软件可以做网站,餐饮vi设计手册题目名称#xff1a;
杨氏矩阵
题目内容#xff1a;
有一个数字矩阵#xff0c;矩阵的每行从左到右是递增的#xff0c;矩阵从下到上递增的#xff08;杨氏矩阵的定义#xff09;#xff0c;请编写程序在这样的矩阵中查找某个数字是否存在。
形如这样的矩阵就是杨氏…题目名称
杨氏矩阵
题目内容
有一个数字矩阵矩阵的每行从左到右是递增的矩阵从下到上递增的杨氏矩阵的定义请编写程序在这样的矩阵中查找某个数字是否存在。
形如这样的矩阵就是杨氏矩阵本质上是一个二维数组 要求
时间复杂度小于O(N)
解题思路
因为题目要求时间复杂度小于ON所以我们不能用暴力枚举遍历去解决这道题。
如何去简化时间复杂度呢
我们首先要知道具体简化的点在哪里ON是因为我们遍历一个一个去排除最差的情况下我们需要排除n次因为遍历一次排除1个。那我们就有这样的简化思想遍历一次可以排除多个元素这样时间复杂度肯定小于ON。
带着这样的思路去想我们发现最右上角的元素很特殊。
因为它是一行中最大的元素也是一列中最小的元素。
如果比它小直接排除列。
如果比它大直接排除行。
并且这样的方法可以一直循环下去直到遍历完整个数组
这也就相当于我们遍历了一个元素可以排除一行/一列的元素大大减少了时间复杂度满足题目要求。
TIP如何自定义函数返回两个值
我们知道函数的返回值只能返回一个值如果题目要求我们返回两个甚至更多的值怎么办呢
这个时候我们就可以利用函数的参数我们传参传我们需要返回参数的地址过去这样在自定义函数中我们就可以返回我们想要的参数
源码
int young_search(int arr[3][3], int row, int col, int k, int* x, int* y)
{int ret 0;while (ret row col 0){if (arr[ret][col - 1] k){*x ret 1;*y col;return 1;}else if (arr[ret][col - 1] k){col--;}else{ret;}}return 0;
}int main()
{int arr[3][3] { 1,2,3,4,5,6,7,8,9 };int k 2;int x 0;int y 0;int ret young_search(arr, 3, 3, k,x,y);if (ret 1)printf(找到了下标是%d,%d, x, y);elseprintf(找不到);return 0;
}
