内容简介:题目:杨氏矩阵(一个二维数组,数组的每行从左到右是递增的,每列从上到下是递增的)在这样的数组中查找一个数字是否存在。
题目:
杨氏矩阵(一个二维数组,数组的每行从左到右是递增的,每列从上到下是递增的)
在这样的数组中查找一个数字是否存在。
要求时间复杂度小于O(N);
主要思路:
题目要求时间复杂度度不能大于O(N),所以判断次数必须小于遍历一次数组次数。
所以从数组的右上角开始判断,若当前元素大于要查找的数字,则跳过当前列查询下一列,若当前元素小于要查找的数,则跳过当前行查找下一行,直至找到或者找不到。
eg:
此处使用数组arr[3][3]={1,2,3,4,5,6,7,8,9};
1 2 3
4 5 6
7 8 9
在数组中朝查找5,首先判断3<5,则查找范围就变成了
4 5 6
7 8 9
再判断6>5,则查找范围又变为了
4 5
7 8
这时候再判断5=5
则找到
源代码:
#include<stdio.h> #include<stdlib.h> void find(int arr[][3],int *row, int *col,int key) { int x = 0; int y = *col - 1; while (x <*row&&y>0)//判断条件 { if (arr[x][y] == key)//找到 { *row = x; *col = y; return; } else if (arr[x][y] < key) { x++;//变换行 } else { y--;//变换列 } } *row = -1; *col = -1; } int main() { int arr[3][3]= {1,2,3,4,5,6,7,8,9}; int x=3; int y=3; int *row = &x; int *col = &y; int key=5; find(arr,row,col,key); if (*row == -1 && *col == -1) { printf("没找到\n"); } else { printf("找到了,下标为%d %d\n", *row, *col); } system("pause"); return 0; }
Linux公社的RSS地址 : https://www.linuxidc.com/rssFeed.aspx
本文永久更新链接地址: https://www.linuxidc.com/Linux/2019-04/158372.htm
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 在R中查找矩阵中的模式
- 机器学习 | SVD矩阵分解算法,对矩阵做拆分,然后呢?
- golang 算法-矩阵
- 彻底理解矩阵乘法
- [开源项目]矩阵数据的意义
- iphone – :CGAffineTransformInvert:奇异矩阵
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
火的礼物:人类与计算技术的终极博弈(第4版)
【美】Baase,Sara(莎拉芭氏) / 郭耀、李琦 / 电子工业出版社 / 89.00
《火的礼物:人类与计算技术的终极博弈 (第4版)》是一本讲解与计算技术相关的社会、法律和伦理问题的综合性读物。《火的礼物:人类与计算技术的终极博弈 (第4版)》以希腊神话中普罗米修斯送给人类的火的礼物作为类比,针对当前IT技术与互联网迅速发展带来的一些社会问题,从法律和道德的角度详细分析了计算机技术对隐私权、言论自由、知识产权与著作权、网络犯罪等方面带来的新的挑战和应对措施,讲解了计算技术对人类的......一起来看看 《火的礼物:人类与计算技术的终极博弈(第4版)》 这本书的介绍吧!