Всем привет!
Решал задачу с
https://www.hackerrank.com/challenges/climbing-the...
Вкратце: есть турнирная таблица (scores), где у игроков с одинаковыми очками одинаковое место в таблице и список очков у игрока(alice) после каждой игры. На выходе надо вернуть метро в турнирной таблице после каждой игры.
Сразу очевидным решением показалось
def climbingLeaderboard(scores, alice):
return [sorted(set(scores + [ball]), reverse=True).index(ball) + 1 for ball in alice]
Но такой алгоритм оказался не оптимальным, так как некоторые тесты падали по таймауту. Сложность я оценил как O(len(scores) * len(alice))
Верным оказалось такое решение:
def climbingLeaderboard(scores, alice):
res = []
scores = sorted(set(scores), reverse=True)
i = len(scores)
for b in alice:
while (i > 0) and (b >= scores[i-1]):
i -= 1
res.append(i + 1)
return res
Как в таком случае посчитать сложность алгоритма ? scores и alice - списки разной длины scores > alice.
Также хотелось бы узнать ваше мнение по такому вопросу: такой навык, как нахождение оптимального алгоритма можно натренировать постоянным решением подобных задач ? Дело в том, что встретив такую задачу в реальной жизни, я бы никогда не подумал написать что-то кроме решения 1, и на данный момент, мне кажется, что решение большого количества таких задач это не изменило бы.
