在行列都排好序的矩阵中找指定的数

[编程题]在行列都排好序的矩阵中找指定的数

热度指数：23740 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 $N \times M$ 的整形矩阵matrix和一个整数K, matrix的每一行和每一列都是排好序的。

实现一个函数，判断K是否在matrix中

[要求]

时间复杂度为

，额外空间复杂度为

。

输入描述:

第一行有三个整数N, M, K
接下来N行，每行M个整数为输入的矩阵

输出描述:

若K存在于矩阵中输出"Yes"，否则输出"No"

示例1

输入

2 4 5
1 2 3 4
2 4 5 6

输出

Yes

示例2

输入

2 4 233
1 2 3 4
2 4 5 6

输出

No

备注:

算法知识视频讲解

Scala

pein531

利用行和列都排好序的信息，从右上角开始搜索，遇到大于target的元素，就往左边的列继续找，遇到小于target的元素就往下面的行继续找。最差情况从右上角移动到左下角才找到，算法的时间复杂度为O(N+M)，仅使用有限几个变量(行指针和列指针)，空间复杂度为O(1)

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"
    }
}

发表于 2021-11-19 22:37:46 回复(0)