剑指Offer刷题记录,第二题。

剑指 Offer 04. 二维数组中的查找(medium)


方法一:二分法+双指针

思路:观察可知,左下角的数组值是其所在行最小值且为所在列最大值,于是有:
(1) 如果 左下角元素大于目标值,则目标值一定位于该行的上方, 左下角元素所在行可以消除。
(2) 如果 左下角元素小于目标值,则目标值一定位于该列的右方, 左下角元素所在列可以消除。
注:其实从左下角和右上角开始走,都是相同的思路。

class Solution {
   
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
   
        // 特例
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    // 当数组不存在,或为空时,直接返回false。
            return false;
        }
        // 二分查找
        int n = matrix.length, m = matrix[0].length; // 行标和列表
        int i = n - 1, j = 0; // 从左下角开始遍历
        while (i >= 0 && j < m) {
   
            if (matrix[i][j] > target) {
    // 当前值大于目标值,则说明当前值所在行都大于目标值,因此,需要消除该行。
                i -= 1;
            }else if (matrix[i][j] < target) {
    // 当前值小于目标值,则说明当前值所在列都小于目标值,因此,需要消除该列。
                j += 1;
            }else{
    // 查找到目标值,返回true。
                return true;
            }
        }
        return false; // 未找到目标值,返回false。
    }
}

时间复杂度:O(M + N), N和M分别为数组行数和列数,该算法最多循环M + N 次。
空间复杂度:O(1), 未使用额外空间。

全部评论

相关推荐

星辰再现:裁员给校招生腾地方
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务