我要招人

去企业版

首页 > 试题广场 >

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

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

热度指数：23938 时间限制：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

备注:

算法知识视频讲解

Sookier

package main

import (

"fmt"

"bufio"

"strings"

"strconv"

"os"

)

func main() {

var (

k int

index int

max_num int

)

in := bufio.NewScanner(os.Stdin)

for in.Scan() {

strs := strings.Split(in.Text(), " ")

if index == 0 {

k, _ = strconv.Atoi(strs[len(strs)-1])

}else {

max_num, _ = strconv.Atoi(strs[len(strs)-1])

}

index = index + 1

}

if max_num > k {

fmt.Println("Yes")

}else {

fmt.Println("No")

}

发表于 2022-11-16 15:06:47 回复(0)

<云昊>

package main
import (
    "fmt"
)

func main() {
    var (
        N int
        M int 
        K int
        n int
    )
    fmt.Scan(&N,&M,&K)
    nums := make([][]int,N)
    for i:=0;i<N;i++ {
        nums[i] = make([]int,M)
        for j:=0;j<M;j++ {
            fmt.Scan(&n)
            nums[i][j] = n
        }
    }
    result := find(nums,K)
    fmt.Println(result)
}

func find(nums [][]int,target int) string {
    rows,cols := len(nums), len(nums[0])
    row, col := 0,cols-1
    for row = 0 {
        if nums[row][col] == target {
            return "Yes"
        } else if nums[row][col] > target {
            col -- 
        } else {
            row++
        }
    }
    return "No"
}

发表于 2021-11-06 08:45:03 回复(0)