做甜品网站的需求分析,郑州修了你官方网站,网站开发人员必备技能,商铺装修找什么公司★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号#xff1a;山青咏芝#xff08;shanqingyongzhi#xff09;➤博客园地址#xff1a;山青咏芝#xff08;https://www.cnblogs.com/strengthen/#xff09;➤GitHub地址山青咏芝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: trueExample 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 false5 }6 7 let rows matrix.count8 let columns matrix[0].count9
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 mid1
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 false5 }6 7 let n matrix.count8 let m matrix[0].count9 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 false5 }6 // 边界判断7 if target matrix.first!.first! || target matrix.last!.last! {8 return false9 }
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 - 16 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 ) / 29 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 } 转载于:https://www.cnblogs.com/strengthen/p/9929505.html
