给定一个
的整形矩阵matrix和一个整数K, matrix的每一行和每一列都是排好序的。
实现一个函数,判断K是否在matrix中
[要求]
时间复杂度为
,额外空间复杂度为
。
第一行有三个整数N, M, K
接下来N行,每行M个整数为输入的矩阵
若K存在于矩阵中输出"Yes",否则输出"No"
2 4 5 1 2 3 4 2 4 5 6
Yes
2 4 233 1 2 3 4 2 4 5 6
No
import scala.io.StdIn
object Main{
def main(args: Array[String]): Unit = {
val in = StdIn
var params = in.readLine().split(" ")
val n = params(0).toInt
val m = params(1).toInt
val k = params(2).toInt
val arr = Array.ofDim[Int](n, m)
for(i <- arr.indices){
params = in.readLine().split(" ")
for(j <- arr(0).indices)
arr(i)(j) = params(j).toInt
}
println(search(arr, n, m, k))
}
def search(arr: Array[Array[Int]], n: Int, m: Int, k: Int): String = {
var row = 0
var col = m - 1
while(row < n && col >= 0){
if(arr(row)(col) > k){
col -= 1
}else if(arr(row)(col) < k){
row += 1
}else{
return "Yes"
}
}
"No"
}
}