Cod sursa(job #2536793)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 2 februarie 2020 17:38:58
Problema Statistici de ordine Scor 100
Compilator py Status done
Runda Arhiva educationala Marime 0.59 kb
import random

def nth_element(v : list, k : int):
    if len(v) == 1:
        return v[0]

    a = random.choice(v)
    small = [i for i in v if i < a]
    big = [i for i in v if i > a]
    eq = [i for i in v if i == a]

    if len(small) >= k:
        return nth_element(small, k)
    else:
        k -= len(small)
    if len(eq) >= k:
        return a
    return nth_element(big, k - len(eq))

fin = open("sdo.in", "r")

n, k = [int(x) for x in fin.readline().split()]
v = [int(x) for x in fin.readline().split()]

fout = open("sdo.out", "w")
fout.write(str(nth_element(v, k)))