首页 > 试题广场 >

有序矩阵中第K小的元素

[编程题]有序矩阵中第K小的元素

热度指数：5265 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个元素。

示例:

matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

返回 13。
说明:
你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

输入描述:

第一行为k的值和矩阵的n的值

后续为n*n矩阵的数字，以空格分割

输出描述:

矩阵中第k小的元素

示例1

输入

输出

算法知识视频讲解

JavaScript

萌萌萌哒

JavaScript(Node) 😎题目:唯品会💄-有序矩阵中第K小的元素(sort就完事了)

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
let n
rl.on('line',line=>{
    if(!line) return
    inArr.push(line)
    if(inArr.length === 1){
        k = +inArr[0].split(' ')[0]
        n = +inArr[0].split(' ')[1]
    }
    if(inArr.length === n+1){
        let res = []
        let ans
        for (let i = 0; i < n; i++) {
             res[i] = inArr[i+1].split(' ').map(e => +e)
        }
        res = [].concat(...res).sort((a,b) => a-b)
        ans = res[k-1]
        console.log(ans)
    }
})

发表于 2020-03-01 17:36:49 回复(0)