algorithm - 从分数列表生成标准比赛排名

Question

给定分数列表(例如 5、5、4、2、2、0)，我希望返回标准比赛排名(1、1、3、4、4、6)。

来自 Wikipedia's ranking page ，这里是 SRC 的总结:

Standard competition ranking ("1224" ranking)

In competition ranking, items that compare equal receive the same ranking number, and then a gap is left in the ranking numbers. The number of ranking numbers that are left out in this gap is one less than the number of items that compared equal. Equivalently, each item's ranking number is 1 plus the number of items ranked above it. This ranking strategy is frequently adopted for competitions, as it means that if two (or more) competitors tie for a position in the ranking, the position of all those ranked below them is unaffected (ie, a competitor only comes second if exactly one person scores better than them, third if exactly two people score better than them, fourth if exactly three people score better than them, etc).

Thus if A ranks ahead of B and C (which compare equal) which are both ranked ahead of D, then A gets ranking number 1 ("first"), B gets ranking number 2 ("joint second"), C also gets ranking number 2 ("joint second") and D gets ranking number 4 ("fourth"). In this case, nobody would get ranking number 3 ("third") and that would be left as a gap.

任何语言的代码都会很有帮助。

顺便说一句，我有兴趣了解其他排名类型(修改后的竞争排名、密集排名、顺序排名和分数排名)的算法。

Answer 1

方法如下:

• 将 ranking[0] 设置为 1。
• 对于 score 列表中的每个索引 i
  • 如果 score[i] 等于 score[i-1] 他们应该有相同的排名:
    • 排名[i] = ranknig[i-1]
  • 否则排名应该等于当前索引:
    • ranking[i] = i + 1
      (+ 1 由于基于 0 的索引和基于 1 的排名)

这是 Java 中的示例实现:

// Set up some sample scores.
int[] scores = { 5, 5, 4, 2, 2, 0 };

// Initialize a ranking array
int[] rankings = new int[scores.length];

// Fill in each position
rankings[0] = 1;
for (int i = 1; i < rankings.length; i++)
    rankings[i] = scores[i] == scores[i-1] ? rankings[i-1] : i + 1;

// rankings = [1, 1, 3, 4, 4, 6]