leetCode 240: Search a 2D Matrix

题目

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
写一个搜索M 乘N矩阵的高效率方法，矩阵有以下特性：

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,
Consider the following matrix:

[
  [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]
]

思想

• 因为矩阵在行与列是有序的，根据它的特性，左上角的数值A和右下角的数值B决定了矩阵的上界和下界。如果target不在区间[A, B]之中，说明肯定不存在这个矩阵里面。

• 把矩阵每次都分成4份，然后用小矩阵的上下界来判断target是否有可能在里面。如果有可能在的话，则继续分成4份，递归查找。如果没有可能的话，就停止，不需要再找了。

  
  区间上下界

• 递归结束条件：最终只有一行或者一列的时候，是不可能再分了，这个时候就需要一个个比较判断target是否存在了。

实现

假设一开始数组的坐标为(SR, SC) ，而数组行数为RL，列数为CL， 则坐标如下图所示：

拆分视图

判断target是否有可能在某个区间内

我们只需要让target与(SR, SC) 和 (SR + RL - 1, CR + CL - 1)的元素值进行比较，就可以判断target是否有可能在该方格中。

/// 判断target是否在该区间中
    ///
    /// - Parameters:
    ///   - matrix: 二维数组
    ///   - target: target
    ///   - rowStartIndex: 起始行下标
    ///   - columnStartIndx: 起始列下标
    ///   - row: 区间行数
    ///   - column: 区间列数
    /// - Returns: 是否可能存在该区间中
    func isTargetInRange(_ matrix:[[Int]], _ target: Int, rowStartIndex: Int, columnStartIndx: Int, row: Int, column: Int) -> Bool {
        if target < matrix[rowStartIndex][columnStartIndx] || target > matrix[rowStartIndex + row - 1][columnStartIndx + column - 1] {
            return false
        }
        
        return true
    }

拆分区间

将一个大的区间拆分成4份小区间，也就是取行数、列数的一半，然后下标则如下图所示：

拆分下标

直接搜索

当区间的行数或者列数变成1的时候，已经不能再进行拆分了，这时候就可以直接遍历搜索了。如果已经找到了target则直接返回，而无需在别的区间寻找，方法的isFound变量就是这个作用。

最后搜索的方法如下：

/// 是否在该区间找到target
    ///
    /// - Parameters:
    ///   - matrix: 二维数组
    ///   - target: target
    ///   - rowStartIndex: 起始行下标
    ///   - columnStartIndx: 起始列下标
    ///   - row: 区间行数
    ///   - column: 区间列数
    /// - Returns: 是否在该区间找到target
    func searchTarget(_ matrix:[[Int]], _ target: Int, rowStartIndex: Int, columnStartIndx: Int, row: Int, column: Int) -> Bool  {
        let isIn = isTargetInRange(matrix, target, rowStartIndex: rowStartIndex, columnStartIndx: columnStartIndx, row: row, column: column)
        
        if !isIn {
            return false
        }
        
        if row == 1 {
            // 一横的情况
            for item in matrix[rowStartIndex] {
                if item == target {
                    return true
                }
            }
            
            return false
        }
        else if column == 1 {
            // 一竖的情况
            for index in 0..<row {
                if target == matrix[rowStartIndex + index][columnStartIndx] {
                    return true
                }
            }
            
            return false
        }
        
        // 这里需要继续递归
        let newRow = row / 2
        let newColumn = column / 2
        
        // 总共4个递归
        // 是否已经找到的标志，如果找到了，就不需要再去别的区间找了。
        var isFound = false
        
        // 左上方
        isFound = searchTarget(matrix, target, rowStartIndex: rowStartIndex, columnStartIndx: columnStartIndx, row: newRow, column: newColumn)
        
        if isFound {
            return isFound
        }
        
        isFound = searchTarget(matrix, target, rowStartIndex: rowStartIndex + newRow, columnStartIndx: columnStartIndx, row: row - newRow, column: newColumn)
        
        if isFound {
            return isFound
        }
        // 右上方
        isFound = searchTarget(matrix, target, rowStartIndex: rowStartIndex, columnStartIndx: columnStartIndx + newColumn, row: newRow, column: column - newColumn)
        
        if isFound {
            return isFound
        }
        // 右下方
        isFound = searchTarget(matrix, target, rowStartIndex: rowStartIndex + newRow, columnStartIndx: columnStartIndx + newColumn, row: row - newRow, column: column - newColumn)
        
        return isFound
    }