offer 04 二维数组的查找(二叉树)
文章目录
二维数组的查找
在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
暴力解法
就是遍历mn次,找到对应target,返回true或者false,时间复杂度为 O(NM) 。暴力法未利用矩阵 “从上到下递增、从左到右递增” 的特点,显然不是最优解法。
二叉树解法
利用从左到右递增,从上到下递增
向左旋转45,找右上角或者左下角,按照二叉树做,
右上角往下递增,往左递减,
左下角往上递减,往右递增。
这样只需要判断当前值和目标值谁打谁小,判断怎么走(去新的一行或者列,)大体趋势,然后到下一个值再判断和目标值的大小,再走,这样省时间也减少运算量。
matrix.length //矩阵行数
matrix[0].length //矩阵列数
不能忽略输入的数组如果是空数组,要写一个判断
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论