k-th smallest element

mail@pastecode.io avatar
unknown
python
2 years ago
587 B
49
Indexable
Never
import bisect
from collections import deque
B = list(map(int,input().split()))
n = B[0]
k = B[1]
A = list(map(int,input().split()))
ans = ''


tmpl = A[:k]                     #[9,8]   Left
tmpr = deque(A[k:])              #[1,2,0] Right
tmpl.sort()                      #[8,9]   sort left
ans = ans + str(tmpl[k-1]) + ' '

for i in range(n-k):
    bisect.insort(tmpl, tmpr[0]) #Binary search and insert -> O(log(n))
    tmpr.popleft()               #pop tmpr[0]
    ans = ans + str(tmpl[k-1]) + ' '
    
                                 # O((n-k)*log(n)) 
print(ans)