时间戳

首页 > 解决方案 > 优化密集排名算法的性能

javascript - 优化密集排名算法的性能

问题描述

与排行榜相比，我正在做这个挑战来为玩家的得分分配密集的排名。我的以下代码有效，但运行时间太长（站点上的某些测试因超时错误而失败）。

我想知道我还能优化什么？有任何想法吗？

function climbingLeaderboard(scores, alice) {
  const reducedScores = getReducedScores(scores)
  let lastIdxHit = reducedScores.length - 1
  return alice.map((a) => {
    for (let i = lastIdxHit; i >= 0; i--) {
      const rs = reducedScores[i]
      if (a < rs.value) {
        return rs.rank + 1
      }
      lastIdxHit = i - 1
    }
    return 1
  })
}

function getReducedScores(scores) {
  let rank = 0
  return scores.reduce((acc, s) => {
    if (last(acc) && last(acc).value === s) {
      return acc
    }
    rank++
    return acc.concat({ value: s, rank })
  }, [])
}

function last(arr) {
  return arr[arr.length - 1]
}

标签： javascriptalgorithmperformance

解决方案

您的代码对 in 中的每个alice[]值执行完整搜索scores以确定其排名，因此时间复杂度是 quadratic O(n*m)。

但是两个数组都是排序的scores is in descending order. alice are in ascending order.

我们可以利用这一事实进行线性搜索。

在此 Python 代码中，第一部分在数组末尾找到排名。

然后为每个alice元素寻找合适的位置，并rank在scores更改时进行更正。

scores = [100, 100, 50, 40, 40, 20, 10]
alice = [5, 25, 50, 120]

#scores = [100, 90, 90, 80, 75, 60]
#alice = [50, 65, 77, 90, 102]

n = len(scores)
m = len(alice)
rank = 1
for i in range(1, len(scores)):
    if scores[i] < scores[i-1]:
        rank +=1

j = len(scores) - 1
for a in alice:
    while j >= 0 and a >= scores[j]:
        j -=1
        if (j < 0) or (scores[j] > scores[j+1]):
            rank -=1
    print(rank+1)

output
  6 4 2 1
  #6 5 4 2 1

索引和score索引都只在一个方向上移动（向前和向后），所以复杂度是线性的jaliceiO(m+n)

推荐阅读