題目
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]
]
思想
因為矩陣在行與列是有序的笛洛，根據(jù)它的特性纹腌，左上角的數(shù)值A(chǔ)和右下角的數(shù)值B決定了矩陣的上界和下界檐薯。如果target不在區(qū)間[A, B]之中耍铜，說明肯定不存在這個矩陣?yán)锩妗?/p>
-
把矩陣每次都分成4份，然后用小矩陣的上下界來判斷target是否有可能在里面制轰。如果有可能在的話灯谣，則繼續(xù)分成4份，遞歸查找曲掰。如果沒有可能的話疾捍，就停止，不需要再找了栏妖。
區(qū)間上下界 遞歸結(jié)束條件：最終只有一行或者一列的時候乱豆，是不可能再分了，這個時候就需要一個個比較判斷target是否存在了吊趾。
實現(xiàn)
假設(shè)一開始數(shù)組的坐標(biāo)為(SR, SC) 宛裕，而數(shù)組行數(shù)為RL，列數(shù)為CL趾徽， 則坐標(biāo)如下圖所示：
判斷target是否有可能在某個區(qū)間內(nèi)
我們只需要讓target與(SR, SC) 和 (SR + RL - 1, CR + CL - 1)的元素值進行比較续滋，就可以判斷target是否有可能在該方格中。
/// 判斷target是否在該區(qū)間中
///
/// - Parameters:
/// - matrix: 二維數(shù)組
/// - target: target
/// - rowStartIndex: 起始行下標(biāo)
/// - columnStartIndx: 起始列下標(biāo)
/// - row: 區(qū)間行數(shù)
/// - column: 區(qū)間列數(shù)
/// - Returns: 是否可能存在該區(qū)間中
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
}
拆分區(qū)間
將一個大的區(qū)間拆分成4份小區(qū)間孵奶，也就是取行數(shù)疲酌、列數(shù)的一半，然后下標(biāo)則如下圖所示：
直接搜索
當(dāng)區(qū)間的行數(shù)或者列數(shù)變成1的時候了袁，已經(jīng)不能再進行拆分了朗恳，這時候就可以直接遍歷搜索了。如果已經(jīng)找到了target則直接返回载绿，而無需在別的區(qū)間尋找粥诫，方法的isFound變量就是這個作用。
最后搜索的方法如下：
/// 是否在該區(qū)間找到target
///
/// - Parameters:
/// - matrix: 二維數(shù)組
/// - target: target
/// - rowStartIndex: 起始行下標(biāo)
/// - columnStartIndx: 起始列下標(biāo)
/// - row: 區(qū)間行數(shù)
/// - column: 區(qū)間列數(shù)
/// - Returns: 是否在該區(qū)間找到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
}
// 這里需要繼續(xù)遞歸
let newRow = row / 2
let newColumn = column / 2
// 總共4個遞歸
// 是否已經(jīng)找到的標(biāo)志崭庸，如果找到了怀浆，就不需要再去別的區(qū)間找了。
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
}
