V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
luckysc
V2EX  ›  算法

[请教] 剑指 offer-二维数组中的查找-时间复杂度

  •  
  •   luckysc · 2019-09-04 18:15:57 +08:00 · 2895 次点击
    这是一个创建于 1907 天前的主题,其中的信息可能已经有所发展或是发生改变。
    public static boolean find(int[][] matrix, int number) {  
            // 输入条件判断  
            if (matrix == null || matrix.length < 1 || matrix[0].length < 1) {  
                return false;  
            }  
            int rows = matrix.length; // 数组的行数  
            int cols = matrix[1].length; // 数组行的列数  
            int row = 0; // 起始开始的行号  
            int col = cols - 1; // 起始开始的列号  
            // 要查找的位置确保在数组之内  
            while (row >= 0 && row < rows && col >= 0 && col < cols) {  
                if (matrix[row][col] == number) { // 如果找到了就直接退出  
                    return true;  
                } else if (matrix[row][col] > number) { // 如果找到的数比要找的数大,说明要找的数在当前数的左边  
                    col--; // 列数减一,代表向左移动  
                } else { // 如果找到的数比要找的数小,说明要找的数在当前数的下边  
                    row++; // 行数加一,代表向下移动  
                }  
            }  
            return false;  
        }  
    

    这个算法时间复杂度是?

    luckysc
        1
    luckysc  
    OP
       2019-09-04 18:16:25 +08:00
    是 O(2n) 也就是 O (n) ?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2689 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 03:10 · PVG 11:10 · LAX 19:10 · JFK 22:10
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.