[Swift]LeetCode74. 搜索二維矩陣 | Search a 2D Matrix

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公眾號：山青詠芝（shanqingyongzhi）
?博客園地址：山青詠芝（https://www.cnblogs.com/strengthen/）
?GitHub地址：https://github.com/strengthen/LeetCode
?原文地址：https://www.cnblogs.com/strengthen/p/9929505.html?
?如果鏈接不是山青詠芝的博客園地址，則可能是爬取作者的文章。
?原文已修改更新！強烈建議點擊原文地址閱讀！支持作者！支持原創！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Write an efficient algorithm that searches for a value in an?m?x?n?matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [[1,   3,  5,  7],[10, 11, 16, 20],[23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

Input:
matrix = [[1,   3,  5,  7],[10, 11, 16, 20],[23, 30, 34, 50]
]
target = 13
Output: false

---

編寫一個高效的算法來判斷?m?x?n?矩陣中，是否存在一個目標值。該矩陣具有如下特性：

• 每行中的整數從左到右按升序排列。
• 每行的第一個整數大于前一行的最后一個整數。

示例?1:

輸入:
matrix = [[1,   3,  5,  7],[10, 11, 16, 20],[23, 30, 34, 50]
]
target = 3
輸出: true

示例?2:

輸入:
matrix = [[1,   3,  5,  7],[10, 11, 16, 20],[23, 30, 34, 50]
]
target = 13
輸出: false

---

16ms

class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        guard matrix.count > 0 else {
            return false
        }
        
        let rows = matrix.count
        let columns = matrix[0].count
        
        var first = 0
        var last = rows*columns-1
        
        while first <= last {
            let mid = first + (last-first)/2
            
            if matrix[mid/columns][mid%columns] == target {
                return true
            }
            
            if matrix[mid/columns][mid%columns] > target {
                last = mid-1
            }
            else {
                first = mid+1
            }
        }
        
        return false
    }
}

---

16ms

class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        if matrix.count == 0 || matrix[0].count == 0 {
            return false
        }

        let n = matrix.count
        let m = matrix[0].count
        var left = 0
        var right = m * n - 1

        while left < right {
            let middle = left + (right - left - 1) / 2
            if matrix[middle / m][middle % m] < target {
                left = middle + 1
            } else {
                right = middle
            }
        }

        return matrix[right / m][right % m] == target
    }
}

---

20ms

class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        if matrix.count == 0 || matrix.first!.count <= 0 {
            return false
        }
        // 邊界判斷
        if target < matrix.first!.first! || target > matrix.last!.last! {
            return false
        }
        // 因為矩陣的每行都有序, 可將矩陣看作"一個數組"進行二分查找
        var low = 0
        var high = matrix.count * matrix.first!.count - 1
        var mid = 0
        while low <= high {
            mid = (low + high) / 2
            let coords = convertIndex(mid, in: matrix) // index轉換為坐標
            let value = matrix[coords.row][coords.column]
            if value == target {
                return true
            } else if target < value {
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
        return false
    }
    
    private func convertIndex(_ index: Int, in matix: [[Any]]) -> (row: Int, column: Int) {
        return (row: index / matix.first!.count,
                column: index % matix.first!.count)
    }
}

---

80ms

class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        guard !matrix.isEmpty else { return false }

        let lastRowIndex = matrix.count - 1

        for (index, row) in matrix.enumerated() {
            guard !row.isEmpty else { continue }
            guard target >= row[0] else { continue }

            if lastRowIndex != index && target >= matrix[index + 1][0] {
                continue
            }

            for n in row {
                if n == target {
                    return true
                }
            }

        }

        return false
    }
}

---

100ms

class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        let arr = matrix.flatMap{$0}
        return binarySearch(arr, 0, arr.count - 1, target)
    }
    
    func binarySearch(_ arr: [Int], _ start: Int, _ end: Int, _ target: Int) -> Bool {
        let mid = (start + end ) / 2
        guard start <= end else { return false }
        if target == arr[mid] { return true}
        if target < arr[mid] {
            return binarySearch(arr, start, mid - 1, target)
        } else {
            return binarySearch(arr,  mid + 1, end, target)
        }
    }
}

---

104ms

class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        let arr = matrix.flatMap{$0}
        return binarySearch(arr, 0, arr.count - 1, target)
    }
    
    func divide(_ arr: [[Int]], _ start: Int, _ end:Int, _ target: Int) -> Bool {
        guard start <= end else { return false }
        if start == end {
            return binarySearch(arr[start], 0, arr[start].count - 1, target)
        }
        
        let mid = (start + end ) / 2
        let localArr = arr[mid]
        let high = localArr[localArr.count - 1]
        if target == high { return true}
        if high < target {
            return divide(arr, mid + 1, end, target)
        } else {
             return divide(arr, start, mid, target)
        }
    }
    
    func binarySearch(_ arr: [Int], _ start: Int, _ end: Int, _ target: Int) -> Bool {
        let mid = (start + end ) / 2
        guard start <= end else { return false }
        if target == arr[mid] { return true}
        if target < arr[mid] {
            return binarySearch(arr, start, mid - 1, target)
        } else {
            return binarySearch(arr,  mid + 1, end, target)
        }
    }
}

?