c# - HackerRank 攀升排行榜

Question

这个问题与this challenge有关在 HackerRank 上。它似乎在某些情况下失败了，但我不清楚算法有什么问题(很多人似乎有超时问题，这不是问题，一切都运行得很快，我看到的所有情况都通过了，所以我没有失败的具体案例)。

算法工作原理的基本概述如下:首先要确保爱丽丝还没有赢得现有的最高分(退化的情况)，如果她只是告诉世界她从头到尾都是第一名的话。否则，排行榜上至少有一个分数打败了爱丽丝的第一次尝试。

• 从分数列表中从最高分开始，直到我们找到适合 Alice 的位置，然后记录一路上超过 Alice 初始分数的分数。
• 如果我们在找到爱丽丝最低分数的位置之前到达分数列表的末尾，假设列表底部有一个分数与爱丽丝的第一个分数相匹配(这只是为了方便主循环并减少问题到爱丽丝的第一个分数在列表某处的地方)

此时我们有一个(排序的)分数数组及其相关排名，rankAry[r - 1] 是 Alice 在第一个 while 循环之后的 if 子句结束时达到排名 r 所需的最低分数.

从那里开始，主要算法接管我们遍历 Alice 的分数，并通过与我们之前设置为 rankAry 的分数数组中的基准进行比较来记录她的排名。 curRank 是我们在每个阶段的候选排名，我们在这个循环开始时(通过构造)肯定已经达到了这个排名。

• 如果我们在排名 1，我们将永远排名更高，所以只需将当前排名填充为 1 并继续前进。
• 如果我们目前与当前基准持平或超过当前基准，并且这还没有结束，请继续查看下一个基准，如果我们也超过了下一个基准，则降低当前基准位置并迭代<
• 一旦这终止，我们就找到了我们要取代的那个，我们不能再取代任何东西，所以将这个排名分配给这个分数并重复直到完成

据我所知，这可以正确处理所有情况，即使 Alice 在分数的基准之间有重复的值或增加，我们应该保持相同的排名，直到我们达到新的基准，但网站反馈表明必须成为某个地方的错误。

我能找到的所有其他方法似乎都是通过二分搜索每次找到分数的一些变体，但我更喜欢不必每次都不断搜索而只使用辅助空间，所以我我对可能出现的问题感到有点困惑。

static int[] climbingLeaderboard(int[] scores, int[] alice) {
        int[] res = new int[alice.Length];
        if (scores.Length == 0 || alice[0] >= scores[0]) { //degenerate cases
            for (int i = 0; i < alice.Length; ++i) {
                res[i] = 1;
            }
            return res;
        }
        int[] rankAry = new int[scores.Length + 1];
        rankAry[0] = scores[0]; //top score rank
        int curPos = 1; //start at the front and move down
        int curRank = 1; //initialize
        //initialize from the front. This way we can figure out ranks as we go
        while (curPos < scores.Length && scores[curPos] > alice[0]) {
            if (scores[curPos] < scores[curPos-1]) {
                rankAry[curRank] = scores[curPos]; //update the rank break point
                curRank++; //moved down in rank
            }
            curPos++; //move down the array
        }
        if (curPos == scores.Length) { //smallest score still bigger than Alice's first
            rankAry[curRank] = alice[0]; //pretend there was a virtual value at the end
            curRank++; //give rank Alice will have for first score when we get there
        }

        for (int i = 0; i < alice.Length; ++i) {
                if (curRank == 1) { //if we're at the top, we're going to stay there
                    res[i] = 1;
                    continue;
                }

                //Non-degenerate cases
                while (alice[i] >= rankAry[curRank - 1]) {
                        if (curRank == 1 || alice[i] < rankAry[curRank - 2]) {
                            break;
                        }

                        curRank--;
                    }
                res[i] = curRank;
            }

        return res;
    }

Answer 1

您的算法中有几个错误。

映射错误

您的 rankAry 必须将排名(您的索引)映射到分数。但是，对于这一行 rankAry[0] = scores[0];，最高分被映射到 0，但可能的最高排名是 1 而不是 0。因此，将其更改为:

rankAry[1] = scores[0];

错误的初始排名

出于某种原因，您的 curRank 设置为 1，如下所示:

int curRank = 1; //initialize

但是，这是错误的，因为您的 alice[0] 小于 scores[0]，因为在您的方法开始时运行了以下 block :

if (scores.Length == 0 || alice[0] >= scores[0]) { //degenerate cases
    for (int i = 0; i < alice.Length; ++i) {
        res[i] = 1;
    }
    return res;
}

因此，您的 curRank 最多为 2。因此，将其更改为:

int curRank = 2;

然后，您还可以删除 curRank++，因为您的 curRank 具有正确的初始值:

if (curPos == scores.Length) { //smallest score still bigger than Alice's first
    rankAry[curRank] = alice[0]; //pretend there was a virtual value at the end
    curRank++; // it's not longer needed so remove it
}

改进“非退化案例”处理

您的 break 条件应该考虑 rankAry 在 curRank - 1 而不是 curRank - 2 因为它足以检查相邻的等级值。此外，curRank - 2 的值对于某些输入会产生错误的结果，但我不会具体解释哪些情况 - 我会留给您去发现。

固定代码

所以，我根据上面的评论修改了你的方法，它通过了所有测试。在这里。

static int[] climbingLeaderboard(int[] scores, int[] alice) {
    int[] res = new int[alice.Length];
    if (scores.Length == 0 || alice[0] >= scores[0]) { //degenerate cases
        for (int i = 0; i < alice.Length; ++i) {
            res[i] = 1;
        }
        return res;
    }
    int[] rankAry = new int[scores.Length + 1];
    rankAry[1] = scores[0]; //top score rank
    int curPos = 1; //start at the front and move down
    int curRank = 2; //initialize
    //initialize from the front. This way we can figure out ranks as we go
    while (curPos < scores.Length && scores[curPos] > alice[0]) {
        if (scores[curPos] < scores[curPos-1]) {
            rankAry[curRank] = scores[curPos]; //update the rank break point
            curRank++; //moved down in rank
        }
        curPos++; //move down the array
    }

    if (curPos == scores.Length) { //smallest score still bigger than Alice's first
        rankAry[curRank] = alice[0]; //pretend there was a virtual value at the end
    }

    for (int i = 0; i < alice.Length; ++i) {
        if (curRank == 1) { //if we're at the top, we're going to stay there
            res[i] = 1;
            continue;
        }

        //Non-degenerate cases
        while (alice[i] >= rankAry[curRank - 1]) {
            if (curRank == 1 || alice[i] < rankAry[curRank - 1]) {
                break;
            }

            curRank--;
        }
        res[i] = curRank;
    }

    return res;
}