寻找矩阵key

2016-11-19 16:30 阅读 525 次 评论 0 条

00:00/00:00

二维数组中寻找key

问题:有一个二维数组.----杨氏矩阵数组的每行从左到右是递增的,每列从上到下是递增的.在这样的数组中查找一个数字是否存在,时间复杂度小于O(N)。

思路:这道面试题很明显加上了复杂度的概念,O(N)也就是说他的复杂度随事物数量的增加呈线性变化,也就是说说这道题的时候,不能嵌套循环。那么我们就不能像以前那样逐个遍历,寻找矩阵中key的值,首先拿key与矩阵第一行末尾的数来比较,如果key大于它,则说明在下一行,i(行数)++;如果key<它,则说明就在这一行,j(列数)--即可遍历到;最后一种情况也就是刚好是key的值,则直接输出。这样坐下来时间复杂度还是可观的

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:寻找矩阵key | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情