/ * *
The title
Write an efficient algorithm to search a target value in m x n matrix matrix. The matrix has the following properties:
The elements of each row are arranged in ascending order from left to right. The elements of each column are arranged from top to bottom. Example 1:
Input: matrix = [,4,7,11,15 [1], [2,5,8,12,19], [3,6,9,16,22], [10,13,14,17,24], [18,21,23,26,30]], target = 5 output: true example 2:
Input: matrix = [,4,7,11,15 [1], [2,5,8,12,19], [3,6,9,16,22], [10,13,14,17,24], [18,21,23,26,30]], target = 20 output: false
Tip:
m == matrix.length n == matrix[i].length 1 <= n, M <= 300-109 <= matix[I][j] <= 109 All elements of each row are arranged in ascending order from left to right and all elements of each column are arranged in ascending order from top to bottom -109 <= target <= 109
Source: LeetCode link: leetcode-cn.com/problems/se… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
The test code
,4,7,11,15 print (searchMatrix ([[1], [2,5,8,12,19], [3,6,9,16,22], [10,13,14,17,24], [18,21,23,26,30]], 5))
notes
The easiest way to think about this problem is the brute force solution, just going through each line
There’s another clever way to think about it is that you sort the matrix from left to right, from top to bottom and you start at the bottom left and you get this value, which is the minimum value of this row and the maximum value of this column
If the current value is less than the target value, then everything in this column must be less than the target value, so if you go to the right and the current value is greater than the target value, then everything on the right of this row must be greater than the target value, so you just go up and you just keep going until all of the elements are not satisfied
The code address
Github.com/zmfflying/Z… * /
The problem solving code
import Foundation func searchMatrix(_ matrix: [[Int]], _ target: Var I = matrix. Count -1 var j = 0 while I >= 0 &&j < Matrix [I].count {// let num = matrix[I][j] // If num < target {j += 1 } else if num > target {I -= 1} else {return true}} return false //func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool { // for nums in matrix { // if nums.count > 0 && nums.first! <= target && nums.last! >= target { // let set: Set<Int> = Set<Int>(nums) // if set.contains(target) { // return true // } // } // } // return false //}Copy the code