在次线性时间搜索2D数组

Question

这是最近的编码访谈中的问题

编写一个有效的算法来搜索mxn矩阵中的值.

该矩阵具有以下属性:

1. 每行中的整数按从左到右的升序排序.

2. 每列中的整数按从上到下的顺序排序.
   .

     [1,   4,  7, 11, 15]
   
     [2,   5,  8, 12, 19]
   
     [3,   6,  9, 16, 22]
   
     [10, 13, 14, 17, 24]
   
     [18, 21, 23, 26, 30]
   

有没有办法在O(mn)以下执行此操作.我无法看到如何在这个数组上进行二进制搜索,因为没有办法消除任何东西.

Answer 1

您可以使用这个简单的算法，该算法利用了以下事实：在具有这些属性的矩阵中，值mtx[i][j]始终小于任何值，其中或，换句话说，是向右和向下的任何值： mtx[x][y]x > iy > j

public static boolean find(int[][] mtx, int val) {
    int maxCol = mtx[0].length, minCol = 0;

    for(int i = 0 ; i < mtx.length ; i++) {
        for(int j = minCol ; j < maxCol ; j++) {
            if(val == mtx[i][j]) return true;

            if(val < mtx[i][j]) {
                maxCol = j;
                break;
            }
        }

        if(maxCol == 0) break;

        minCol = 0;
        if(i != mtx.length-1 && val > mtx[i+1][maxCol-1]) minCol = maxCol-1;
    }

    return false;
}

这个想法是逐行搜索，如果您发现一个更大的值，您可以停止在该行中查找，并且您知道不必在以后的行中搜索超出该列的内容。如果一行的第一个值大于该值，则可以停止搜索并返回 false。另外，在每行搜索结束时，您检查下一行的单元格maxCol-1，如果值较大，则在下一个循环中，您可以跳过前面的每个单元格。

最坏的情况是最大值（或更大），复杂度为 O(m+n)，因为它会检查所有第一行，然后跳过接下来的 m 行。