提高代码性能:超过时间限制

Question

我为HackerRank任务"爬上排行榜"写了一个解决方案。如果你有一个降序数组(排名)和一个玩家分数的升序数组(玩家)，你应该使用密集排名返回一个包含玩家排名的数组。

我的解决方案似乎是正确的(没有测试用例有错误的答案)，但太慢了。对于3个测试用例，我收到:超过时间限制。

我已经尝试通过以下方式使实现更高效:

• 打破for循环并在玩家到达第一个排名时添加那些(玩家正在上升，所以所有后续排名也将是1)
• 使用指针来避免检查不必要的值(因为玩家是升序和降序)但还是不够快。有人能给我建议如何使我的代码更快?而且它有点长。我相信一定有更简短的表达方式。

我很高兴得到任何关于如何改进我的解决方案的信息。

const oneVector = n => [...Array(n)].map((x, i) => 1);
function climbingLeaderboard(ranked, player) {
// Write your code here
ranked = [...new Set(ranked)];
let pointer;
let ranking = [];
let isFinished;
let nextIndex;
for (let i = 0; i < player.length; i++) {
if (ranking[ranking.length - 1] === 1) {
break;
}
pointer = nextIndex || ranked.length - 1;
isFinished = false;
// smaller than the smallest value
if (i === 0 && player[i] < ranked[ranked.length - 1]) {
ranking.push(ranked.length + 1);
ranked = [...ranked, player[i]];
isFinished = true;
nextIndex = ranked.length;
}
//  bigger than the biggest value
else if (player[i] > ranked[0]) {
ranking.push(1);
ranked = [player[i], ...ranked];
isFinished = true;
nextIndex = 0;
}
// exactly the first value
else if (player[i] === ranked[0]) {
ranking.push(1);
isFinished = true;
nextIndex = 0;
}
while (!isFinished) {
// exactly the value
if (player[i] === ranked[pointer]) {
ranking.push(pointer + 1);
isFinished = true;
nextIndex = pointer;
}
// between values
else if (player[i] > ranked[pointer] && player[i] < ranked[pointer - 1]) {
ranking.push(pointer + 1);
ranked = [
...ranked.slice(0, pointer),
player[i],
...ranked.slice(pointer),
];
isFinished = true;
nextIndex = pointer;
} else {
pointer -= 1;
}
}
}
if (ranking.length < player.length) {
ranking = [...ranking, ...oneVector(player.length - ranking.length)];
}
return ranking;
}

Answer 1

您的

ranked = [...ranked, player[i]];

完全重建了数组，所以是O(N)，我猜你的整个解决方案，O(N*N)在大N

上失败使用ranked.push,ranked.unshift和runked.splice从开始/结束/中间或数组添加/删除项，这些是O(1)

Answer 2

试试这个方法:

function climbingLeaderboard(ranked, player) {
// Remove duplicates from the ranked array
ranked = [...new Set(ranked)];
// Initialize variables
const numPlayers = player.length;
const numRanked = ranked.length;
const result = new Array(numPlayers);
let playerIndex = numPlayers - 1;
let rankedIndex = 0;
// Binary search for player rankings
while (playerIndex >= 0) {
const playerScore = player[playerIndex];
if (rankedIndex === numRanked || playerScore >= ranked[rankedIndex]) {
result[playerIndex] = rankedIndex + 1;
playerIndex--;
} else {
rankedIndex = binarySearch(ranked, playerScore, rankedIndex, numRanked);
}
// Exit early if all players have been ranked
if (rankedIndex === -1) {
break;
}
}
// Set remaining player rankings to the lowest possible ranking
while (playerIndex >= 0) {
result[playerIndex] = 1;
playerIndex--;
}
return result;
}
// Binary search for the index to insert a new score
function binarySearch(arr, val, start, end) {
let left = start;
let right = end - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === val) {
return mid;
} else if (arr[mid] < val) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}

这应该快得多