首页 > 试题广场 >

有序矩阵中第K小的元素

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

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

输入

输出

算法知识视频讲解

Python

卷积神经网络哦

Python三行咯暴力

k, n = [int(x) for x in input().split(' ')]
a = [[int(x) for x in input().split(' ')] for j in range(n)]
print(sorted([y for x in a for y in x])[k-1])

发表于 2019-12-05 09:04:41 回复(0)

Python

我要扛offer回家

import sys
k,n=list(map(int,sys.stdin.readline().split()))
matrix=[]
for i in range(n):
    matrix.extend(list(map(int,sys.stdin.readline().split())))
matrix.sort()
print(matrix[k-1])

编辑于 2019-09-15 11:34:04 回复(0)

Python

牛客835408486号

import math
k, n = list(map(int, input().strip().split()))
matrix = []
for i in range(n):
    matrix.append(list(map(int, input().strip().split())))

count = 0

p = [0 for _ in range(n)]
while True:
    temp = [matrix[i][v] if v != -1 else math.inf for i, v in enumerate(p)]
    m = min(temp)
    row = temp.index(m)
    p[row] += 1
    if p[row] >= n:
        p[row] = -1
    count += 1
    if count >= k:
        print(m)
        break

发表于 2019-09-14 16:05:20 回复(0)

Python

hzdms

heap

import heapq

k, n = list(map(int, input().split()))
matrix = [list(map(int, input().split())) for _ in range(n)]

queue = []
heapq.heapify(queue)

for i in range(n):
    for j in range(n):
        if len(queue) < k:
            heapq.heappush(queue, -matrix[i][j])
        else:
            if matrix[i][j] < -queue[0]:
                heapq.heappop(queue)
                heapq.heappush(queue, -matrix[i][j])
print(-queue[0])

发表于 2019-09-02 03:35:05 回复(0)

Python

贾志统

def func(k, lst):
    lst.sort()
    print(lst[k-1])


k, n = map(int, input().split())
mat_list = []
for i in range(n):
    per_list = list(map(int, input().split()))
    mat_list.extend(per_list)
func(k, mat_list)

发表于 2019-08-31 00:28:53 回复(0)