I hope nobody have posted similar solution (it's tested, but I didn't
submit it to contest):
from bisect import bisect_right as find
def supernumbers(ls):
indices = [0]*len(ls)
for i, e in enumerate(ls):
indices[e - 1] = i
result = [None]*len(ls)
borders = []
for i in indices:
ind = find(borders, i)
result[i] = ind + 1
if ind == len(borders):
borders.append(i)
else:
borders[ind] = i
return result
At least, it looks shorter than other solutins.
Of course, it allows number of optimizations like
prefetching length and caching borders.append.
If I'm correct, it takes O(n*log (max sequence length)) time that can
be a win for huge datasets.
With the best regards,
anton.
--
http://mail.python.org/mailman/listinfo/python-list
