Оптимизация производительности для алгоритма плотного ранжирования

Question

Я делаю это задание , чтобы присвоить плотный рейтинг баллу игрока по сравнению с лидирующей таблицей. Мой следующий код работает, но запускается слишком долго (некоторые тесты на сайте не работают из-за ошибки тайм-аута).

Мне интересно, что еще я могу оптимизировать? Есть идеи?

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]
}

Answer 1

Ваш код выполняет полный поиск каждого значения alice[] в scores, чтобы определить его ранг, поэтому временная сложность равна квадратичному c 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 index j и alice index i перемещаются за одно только направление (вперед и назад), поэтому сложность линейна O(m+n)