K-èsim element P63584

Usant les definicions

implementeu una funció

que retorni el k-èsim element global (començant en u) dels elements continguts en el vector de vectors V. Sigui n = V.size(). Cal tenir en compte que, per a tota 0 ≤ i < n, V[i] està ordenat de petit a gran. A més, no hi ha cap element repetit en tot V.

Per exemple, si k = 5, n = 3, i els tres vectors són

|| V[0]

V[1]

V[2]

||

llavors la resposta és 2, que és el cinquè element més petit de tots els vectors.

Sigui m = ∑₀ⁿ⁻¹ V[i].size(). Podeu suposar que k està entre 1 i m, que n està entre 2 i 500, i que algun V[i] pot estar buit. Si us cal, podeu implementar procediments auxiliars. Tingueu en compte que, en els jocs de proves “grossos”, k = Θ(n) i m = Θ(n²). La solució esperada en aquest cas té cost Θ(n logn).

Observació Només cal enviar el procediment demanat; el programa principal serà ignorat.