Witam,
chcę wykorzystac algorytm Hoare'a do zadania http://pl.spoj.pl/problems/KC022
Czy ma ktos pomysł jak przerobic ten algorytm aby wyszukiwal k-ty największy element tego ciągu tzn.
element który ma k-1 wiekszych elementów.
Zaimplementowalem tylko wersje podstawową tego algorytmu która dla danych
3 10 20 30
zwraca 30 a chcę żeby 10 zwracała na wyjscie.
def alg(a,k):
l=0
r=len(a)-2
#i=j=x=0
while(l<r):
x=a[k]
i=l
j=r
while 1:
while(a[i]<x):
i+=1
while(x<a[j]):
j-=1
if i<=j:
w=a[i]
a[i]=a[j]
a[j]=w
i+=1
j-=1
else:
break
if j<k:
l=i
if k<i:
r=j
return z[k]
while 1:
try:
tab=map(int,raw_input().split())
except EOFError: break
poz=tab[0]-1
tab.__delitem__(0)
z=list(set(tab))
try:
print alg(z,poz)
except IndexError:
print '-'