[Swift]LeetCode74.搜索二维矩阵|Searcha2DMatrix

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

 1 class Solution {
 2     func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
 3         guard matrix.count > 0 else {
 4             return false
 5         }
 6         
 7         let rows = matrix.count
 8         let columns = matrix[0].count
 9         
10         var first = 0
11         var last = rows*columns-1
12         
13         while first <= last {
14             let mid = first + (last-first)/2
15             
16             if matrix[mid/columns][mid%columns] == target {
17                 return true
18             }
19             
20             if matrix[mid/columns][mid%columns] > target {
21                 last = mid-1
22             }
23             else {
24                 first = mid+1
25             }
26         }
27         
28         return false
29     }
30 }

16ms

 1 class Solution {
 2     func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
 3         if matrix.count == 0 || matrix[0].count == 0 {
 4             return false
 5         }
 6 
 7         let n = matrix.count
 8         let m = matrix[0].count
 9         var left = 0
10         var right = m * n - 1
11 
12         while left < right {
13             let middle = left + (right - left - 1) / 2
14             if matrix[middle / m][middle % m] < target {
15                 left = middle + 1
16             } else {
17                 right = middle
18             }
19         }
20 
21         return matrix[right / m][right % m] == target
22     }
23 }

20ms

 1 class Solution {
 2     func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
 3         if matrix.count == 0 || matrix.first!.count <= 0 {
 4             return false
 5         }
 6         // 边界判断
 7         if target < matrix.first!.first! || target > matrix.last!.last! {
 8             return false
 9         }
10         // 因为矩阵的每行都有序, 可将矩阵看作"一个数组"进行二分查找
11         var low = 0
12         var high = matrix.count * matrix.first!.count - 1
13         var mid = 0
14         while low <= high {
15             mid = (low + high) / 2
16             let coords = convertIndex(mid, in: matrix) // index转换为坐标
17             let value = matrix[coords.row][coords.column]
18             if value == target {
19                 return true
20             } else if target < value {
21                 high = mid - 1
22             } else {
23                 low = mid + 1
24             }
25         }
26         return false
27     }
28     
29     private func convertIndex(_ index: Int, in matix: [[Any]]) -> (row: Int, column: Int) {
30         return (row: index / matix.first!.count,
31                 column: index % matix.first!.count)
32     }
33 }

80ms

 1 class Solution {
 2     func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
 3         guard !matrix.isEmpty else { return false }
 4 
 5         let lastRowIndex = matrix.count - 1
 6 
 7         for (index, row) in matrix.enumerated() {
 8             guard !row.isEmpty else { continue }
 9             guard target >= row[0] else { continue }
10 
11             if lastRowIndex != index && target >= matrix[index + 1][0] {
12                 continue
13             }
14 
15             for n in row {
16                 if n == target {
17                     return true
18                 }
19             }
20 
21         }
22 
23         return false
24     }
25 }

100ms

 1 class Solution {
 2     func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
 3         let arr = matrix.flatMap{$0}
 4         return binarySearch(arr, 0, arr.count - 1, target)
 5     }
 6     
 7     func binarySearch(_ arr: [Int], _ start: Int, _ end: Int, _ target: Int) -> Bool {
 8         let mid = (start + end ) / 2
 9         guard start <= end else { return false }
10         if target == arr[mid] { return true}
11         if target < arr[mid] {
12             return binarySearch(arr, start, mid - 1, target)
13         } else {
14             return binarySearch(arr,  mid + 1, end, target)
15         }
16     }
17 }

104ms

 1 class Solution {
 2     func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
 3         let arr = matrix.flatMap{$0}
 4         return binarySearch(arr, 0, arr.count - 1, target)
 5     }
 6     
 7     func divide(_ arr: [[Int]], _ start: Int, _ end:Int, _ target: Int) -> Bool {
 8         guard start <= end else { return false }
 9         if start == end {
10             return binarySearch(arr[start], 0, arr[start].count - 1, target)
11         }
12         
13         let mid = (start + end ) / 2
14         let localArr = arr[mid]
15         let high = localArr[localArr.count - 1]
16         if target == high { return true}
17         if high < target {
18             return divide(arr, mid + 1, end, target)
19         } else {
20              return divide(arr, start, mid, target)
21         }
22     }
23     
24     func binarySearch(_ arr: [Int], _ start: Int, _ end: Int, _ target: Int) -> Bool {
25         let mid = (start + end ) / 2
26         guard start <= end else { return false }
27         if target == arr[mid] { return true}
28         if target < arr[mid] {
29             return binarySearch(arr, start, mid - 1, target)
30         } else {
31             return binarySearch(arr,  mid + 1, end, target)
32         }
33     }
34 }