240. Search a 2D Matrix II

https://leetcode.com/problems/search-a-2d-matrix-ii/description/

题解一

九章算法提供的比较巧妙的解题思路，从matrix 左下角开始向右上角遍历，

初始：

int rowIndex = matrix.length - 1;  
int colIndex = 0;

逻辑主体：

• if currentItem == target, return true;
• if currentItem < target, 则colIndex 所在的列不可能存在 target 的item，colIndex++;
• if currentItem > target, 则 rowIndex 所在的行不可能存在 target 的 item，rowIndex--；

结束条件：
rowIndex < 0 || colIndex > matrix[0].length - 1

example

也可以从右上角开始往左下角遍历，思路类似。

时间复杂度：O(m + n)

代码：

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
        return false;
    }
    
    int row = matrix.length - 1;
    int col = 0;
    while (row >= 0 && col < matrix[0].length) {
        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] < target) {
            col++;
        } else {
            row--;
        }
    }
    return false;
}

---

题解二

尝试着使用二分来进行题解。思路：

• Top row，寻找比 target 小的最大值 index
• Left column，寻找比 target 小的最大值 index
• Bottom row, 寻找比 target 大的最小值 index
• Right column，寻找比 target 大的最小值 index

粗略可以将范围缩小到现有范围的 1/4. loop until rLow > rHigh || cLow > cHigh.

算法复杂度为：

2(log m + log n) + 2(log m/2 + log n/2) + 2*(log m/4 + log n/4) + ...
=> log min(m, n) * (log m + log n)
=> (log m) ^ 2 if m == n

这个解法理论上是比题解一时间复杂度低。但是OJ beats only 2.5%.

代码：

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
        return false;
    }
    
    int rows = matrix.length;
    int cols = matrix[0].length;
    if (matrix[0][0] > target || matrix[rows - 1][cols - 1] < target) {
        return false;
    }
    
    int rLow = 0, rHigh = matrix.length - 1;
    int cLow = 0, cHigh = matrix[0].length - 1;
    int start, end, mid;
    
    while (rLow <= rHigh && cLow <= cHigh) {            
        // find cHigh boundary
        start = cLow;
        end = cHigh;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (matrix[rLow][mid] == target) {
                return true;
            } else if (matrix[rLow][mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        cHigh = end;
                    
        if (cHigh < cLow) {
            return false;
        }
        
        // find rHigh boundary
        start = rLow;
        end = rHigh;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (matrix[mid][cLow] == target) {
                return true;
            } else if (matrix[mid][cLow] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        rHigh = end;
                
        if (rHigh < rLow) {
            return false;
        }
        
        // find cLow boundary
        start = cLow;
        end = cHigh;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (matrix[rHigh][mid] == target) {
                return true;
            } else if (matrix[rHigh][mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        cLow = start;
        
        if (cHigh < cLow) {
            return false;
        }
        
        // find rLow boundary
        start = rLow;
        end = rHigh;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (matrix[mid][cHigh] == target) {
                return true;
            } else if (matrix[mid][cHigh] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        rLow = start;
    }

    return false;
}