最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 题目描述

    在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

    题目分析

    图 1
    如果没有头绪的话,很显然使用 暴力解法 是完全可以解决该问题的。
    即遍历二维数组中的每一个元素,时间复杂度:O(n^2)。
    其实到这里我们就可以发现,使用这种暴力解法并没有充分利用题目给出的信息。这个二维数组是有特点的。
    • 每一行都是递增
    • 每一列都是递增
    图 2

    解法

    解法一:二分法

    对于有序数组的查找问题而言,二分法是最容易想到的一个解法。
    在这里,对每一行使用二分查找,时间复杂度为 O(nlogn) 。二分查找复杂度 O(logn),一共 n 行,所以是总体的时间复杂度是 O(nlogn) 。

    解法二:规律法

    根据二维数组由上到下,由左到右递增的规律。
    从左下角开始遍历,如果当前值比 target 小则往右找,如果比 target 大则往上找,如果存在,必然可以找到目标数字。
    即选取右上角或者左下角的元素 a[row] [col] 与 target 进行比较, 当target小于元素 a[row] [col] 时,那么 target 必定在元素 a 所在行的左边,让 col– ;当 target 大于元素 a[row] [col] 时,那么 target 必定在元素 a 所在列的下边,让 row++ ;
    图 3
    代码如下:
    public class Solution {
         public boolean Find(int target, int [][] array) {
            int row = 0;
            int col = array[0].length – 1;
            while(row <= array.length – 1 && col >= 0){
                if(target == array[row][col])
                    return true;
                else if(target > array[row][col])
                    row++ ;
                else
                    col– ;
            }
            return false;
        }

    }

    解法三:二分规律法

    将解法一和解法二进行结合:对每行每列都使用二分查找,此时的时间复杂度为 O(logn * logm)
    图 4
    比如查找数字 9,首先使用用二分查找选出一行,总共有 5 行,那么( 0 + 5 ) / 2 = 2,所以我们找出了第 2行为基准行。
    图 5
    接下来对这一行(即第 2 行)又使用二分查找, 找出这一行(即第 2 行)中最后一个比目标值小的值,这里是 6。
    图 6
    6 及其所在的行和列把这个矩形划分为 4 部分:
    图 7
    1. 左上部分(图 7 灰色部分),包括所在行的左边部分和所在列的上边部分:这一部分是绝对不会有目标数字的。因为这部分数字肯定比 6 小,而 6 又是小于目标数字的,所以左上部分全部小于目标数字。也就是说这个区域的数字不需要再进行判断了。
    2. 右下部分(图 7 绿色部分),包括所在行的右边部分,但不包括所在列的下面部分, 这一部分也是绝对不会有目标数字的。因为这部分都比 6 右边的数字 11 大,而 11 又比目标数字 9 更大,所以右下部分全部都比目标数字大。也就是说这个区域的数字也不需要再进行判断了。
    3. 左下部分(图 7 蓝色部分),可能含有目标数字。
    4. 右上部分(图 7 棕色部分),可能含有目标数字。
    这样,实际上筛选的区域就只剩下左下部分(图 7 蓝色部分)右上部分(图 7 棕色部分)这两块区域了,相比于解法二而言,使用这种解法平均情况下每一次查找,都可以把行和列的长度减少一半
    代码如下:
    public class Solution {
           public boolean Find(int target, int [][] array) {
           // 特殊情况处理
           if (array == null || array.length == 0 || array[0].length == 0) {
                return false;
            }
            int h = array.length – 1;
            int w = array[0].length – 1;
            // 如果目标值小于最小值 或者 目标值大于最大值,那肯定不存在
            if (array[0][0] > target || array[h][w] < target) {
                return false;
            }
            return binarySearchIn2DArray(array, target, 0, h, 0, w);
        }
         public static boolean binarySearchIn2DArray(int[][] array, int target, int startX, int endX, int startY, int endY) {
            if (startX > endX || startY > endY) {
                return false;
            }
            //首先,根据二分法找出中间行
            int x = (startX + endX) / 2;
            //对该行进行二分查找
            int result = binarySearch(array[x], target, startY, endY);
            //找到的值位于 x 行,result 列
            if (array[x][result] == target) {
                return true// 如果找到则成功
            }
            //对剩余的两部分分别进行递归查找
            return binarySearchIn2DArray(array, target, startX, x – 1, result + 1, endY)
                    || binarySearchIn2DArray(array, target, x + 1, endX, startY, result);
        }
         public static int binarySearch(int[] array, int target, int start, int end) {
            int i = (start + end) / 2;
            if (array[i] == target || start > end) { 
                return i;
            } else if (array[i] > target) {
                return binarySearch(array, target, start, i – 1);
            } else {
                return binarySearch(array, target, i + 1, end);
            }
        }
    }
    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 图解剑指 offer 第一题: 二维数组中的查找

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者
    • 102会员总数(位)
    • 3674资源总数(个)
    • 2本周发布(个)
    • 0 今日发布(个)
    • 136稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级