咨询：编写时间复杂度为O(n)的二维数组值查找方法是否可行

首先直接给结论：是否可行完全取决于你的二维数组m是否具备特定的有序结构——如果是无规则的普通二维数组，这既不可行也不合理；但如果数组是经过有序化设计的（比如杨氏矩阵/行列递增矩阵），那不仅可行，还非常合理。

1. 普通无结构二维数组：不可行也不合理 #

如果你的二维数组是完全无规则的（元素排列没有任何规律），那要确定val是否存在，最坏情况下必须遍历数组中的每一个元素。假设数组有n行，每行平均有k个元素，总元素数是n*k，对应的时间复杂度是O(nk)，远远高于O(n)。

举个极端例子：如果数组是n行1000列的无规则数组，你不可能只检查n个元素就确定val是否存在——因为val完全可能藏在某一行的第500列，你跳过的话就会漏判。这种情况下要求O(n)时间复杂度是不符合逻辑的。

2. 具备有序结构的二维数组：可行且合理 #

最典型的场景是行列都严格递增的二维数组（也叫杨氏矩阵），比如满足：

• 每行元素从左到右递增
• 每列元素从上到下递增
• （或者更严格的：每行的第一个元素大于上一行的最后一个元素）

针对这种结构，我们可以设计一个O(n + m)时间复杂度的查找算法（m是列数），如果数组是n×n的方阵，那时间复杂度就是O(n)，完全符合你的要求。

实现思路 #

从数组的右上角（或左下角）开始遍历：

• 如果当前元素等于val，直接返回true
• 如果当前元素大于val：说明val不可能在当前列（因为列是递增的），向左移动一列
• 如果当前元素小于val：说明val不可能在当前行（因为行是递增的），向下移动一行

每一步操作都会排除一整行或一整列，最坏情况下最多移动n + m次，对于n×n方阵就是O(n)时间。

代码示例 #

public static boolean findValWhat(int[][] m, int val) {
    if (m == null || m.length == 0 || m[0].length == 0) {
        return false;
    }
    
    int rows = m.length;
    int cols = m[0].length;
    // 从右上角开始遍历
    int row = 0;
    int col = cols - 1;
    
    while (row < rows && col >= 0) {
        if (m[row][col] == val) {
            return true;
        } else if (m[row][col] > val) {
            // 当前元素比目标值大，向左缩小范围
            col--;
        } else {
            // 当前元素比目标值小，向下缩小范围
            row++;
        }
    }
    // 遍历结束未找到目标值
    return false;
}

总结 #

• 如果数组是无规则的：要求O(n)时间复杂度不可行，因为无法在不遍历大部分元素的情况下确保不遗漏目标值
• 如果数组是行列递增的有序结构：O(n)（针对方阵）的查找不仅可行，而且是非常高效合理的设计，利用数组的有序性避免了不必要的遍历

内容的提问来源于stack exchange，提问作者Aviv Shvitzky