时间戳

首页 > 解决方案 > 优化黑客排名挑战“攀登排行榜”

ruby - 优化黑客排名挑战“攀登排行榜”

问题描述

挑战是这样的：

爱丽丝正在玩街机游戏，想爬到排行榜的顶端，并想跟踪她的排名。游戏使用密集排名，所以它的排行榜是这样工作的：

得分最高的玩家将在排行榜上排名第一。得分相同的玩家获得相同的排名编号，下一位玩家获得紧随其后的排名编号。例如，排行榜上的四位玩家的高分分别为 100、90、90 和 80。这些玩家的排名分别为 1、2、2 和 3。如果 Alice 的分数是 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

我想知道我能做些什么来优化它？

标签： rubyalgorithmoptimization

解决方案

代码

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

Array#bsearch_index的计算复杂度为 O(log n)，其中n = uniq_rankings.size.

例子

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

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

推荐阅读