如何在满足特定条件的二维方阵中实现O(n)时间复杂度的查找？

First, let's break down what the given test method guarantees about the input matrix:

The test method returns true only if every element in row r is less than or equal to every element in row r+1 for all adjacent row pairs. In other words, the maximum value of row r ≤ the minimum value of row r+1. This means the rows are ordered in a non-decreasing way (all elements in earlier rows ≤ all elements in later rows), even if elements within a row are unordered.

Approach #

Given this structure, we can optimize our search to meet the O(n) time complexity requirement (where n refers to the number of rows):

1. Eliminate irrelevant rows: Since all elements in row r are ≤ all elements in row r+1, if the maximum value of row r is less than val, val can't exist in this row—we skip to the next one.
2. Target the first relevant row: Once we find a row where the maximum value is ≥ val, val could only be in this row (all later rows have elements ≥ this row's max, so they can't contain val if this row doesn't). We then scan this row for the target value.
3. Handle edge cases: We first check for empty or invalid matrices to avoid runtime errors.

Code Implementation #

public boolean findValTest(int[][] m, int val) {
    // Handle empty or invalid matrix
    if (m == null || m.length == 0 || m[0].length == 0) {
        return false;
    }
    
    int n = m.length; // n is the number of rows (and columns, since it's a square matrix)
    
    for (int row = 0; row < n; row++) {
        // Find the maximum value in the current row
        int rowMax = m[row][0];
        for (int col = 1; col < n; col++) {
            if (m[row][col] > rowMax) {
                rowMax = m[row][col];
            }
        }
        
        // If current row's max is smaller than val, skip to next row
        if (rowMax < val) {
            continue;
        }
        
        // Search the current row for val
        for (int col = 0; col < n; col++) {
            if (m[row][col] == val) {
                return true;
            }
        }
        
        // If we reach here, current row has max >= val but no match—later rows can't have val
        return false;
    }
    
    // All rows have max < val
    return false;
}

Why This Works #

• The test method's guarantee lets us safely skip rows that can't contain val—since earlier rows are entirely smaller than later ones, we don't need to revisit them.
• The time complexity is O(n) relative to the number of rows: in the worst case, we scan all n rows to find the relevant one, then scan that row's n elements. This totals O(n + n) = O(n) operations as specified in the problem.

Example Usage #

Using the provided sample array arr3:

int[][] arr3 = new int[][]{
    {0, 2, 1, 2, 0, 5, 5, 5},
    {21, 21, 7, 7, 7, 21, 21, 21},
    {21, 21, 21, 21, 21, 21, 21, 21},
    {21, 21, 23, 42, 41, 23, 21, 21},
    {60, 56, 57, 58, 53, 52, 47, 51},
    {61, 65, 70, 72, 73, 78, 82, 98},
    {112, 121, 112, 134, 123, 100, 98, 111},
    {136, 136, 136, 134, 147, 150, 154, 134}
};

// Returns true (42 exists in the 4th row)
boolean found = findValTest(arr3, 42);
// Returns false (10 doesn't exist in any row)
boolean notFound = findValTest(arr3, 10);

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