Оптимизация задачи хакерского ранга «Восхождение на таблицу лидеров»

Question

Задача такова:

Алиса играет в аркадную игру и хочет подняться на вершину списка лидеров и хочет отследить свой рейтинг. В игре используется Dense Ranking, поэтому ее таблица лидеров работает следующим образом:

Игрок с наибольшим количеством очков занимает номер в таблице лидеров. Игроки, имеющие одинаковые оценки, получают одинаковые рейтинговые номера, а следующие игроки получают сразу же следующий рейтинговый номер. Например, четыре игрока в таблице лидеров имеют высокие оценки 100, 90, 90 и 80. Эти игроки будут иметь рейтинги 1, 2, 2 и 3 соответственно. Если Алиса набрала 70, 80 и 105 баллов, то ее рейтинги после каждой игры - 4-й, 3-й и 1-й

По сути, вы должны возвращать массив с ее рейтингами после каждой игры. У меня есть рабочий код, но время ожидания 4 теста. Вот мой код:

def climbingLeaderboard(scores, alice)
    positions = []
    alice.each do |x|
        scores.insert(scores.index(scores.min_by { |y| (x-y).abs }) + 1, x)
        board = scores.group_by { |x| x }.sort_by { |k,v| v }.reverse
        positions << board.find_index { |k| k[0] == x } + 1
    end
    return positions
end

Мне интересно, что я могу сделать, чтобы оптимизировать его больше?

Answer 1

Код

def climbingLeaderboard(scores, alice)
  uniq_scores = scores.uniq << -1
  alice.map do |alice_score|
    uniq_scores.bsearch_index { |score| alice_score >= score } + 1
  end
end

Массив # bsearch_index имеет вычислительную сложность O (log n), где n = uniq_rankings.size.

Пример

scores = [100, 90, 90, 80]
alice  = [70, 80, 105]

climbingLeaderboard(scores, alice)
  #=> [4, 3, 1]