给定玩家分数统计排名达标人数的最优时间复杂度求解

问题定义 #

给定分数数组scores和整数k，同分玩家排名相同，排名规则为分数高于该玩家的总人数 + 1。例如输入scores = [10, 20, 20, 40]，对应玩家排名为[4, 2, 2, 1]。仅排名小于等于k的玩家可晋级下一轮，要求返回晋级的玩家总人数。

现有解法回顾 #

排序法 #

时间复杂度O(nlogn)，执行步骤：

• 对分数数组做降序排序，耗时O(nlogn)
• 初始化排名rank = 1、晋级人数count = 0，遍历排序后的数组：每遍历到低于上一个的分数时更新rank，只要rank<=k就累计对应分数的玩家数，该步骤耗时O(n)
• 返回累计的晋级人数

哈希表频次统计法 #

时间复杂度O(nk)，执行步骤：

• 遍历数组，用哈希表统计各分数的出现频次，遍历过程中仅保留当前最高的k档分数：如果当前遍历到的分数大于哈希表中存储的最小分数，就删除最小分数对应的条目，存入新分数
• 累加最终哈希表中所有条目的频次值，即为晋级总人数
  该方案实际运行效率通常低于O(nlogn)的排序法。

优化方案 #

方案1：快速选择法（平均时间复杂度O(n)） #

不需要对全量数组排序，仅需定位到排名刚好为k的分数阈值即可：

• 先提取数组中的所有唯一分数
• 用快速选择算法找到唯一分数集合中第k大的分数threshold（如果唯一分数总数不足k，取集合中的最小分数即可）
• 遍历原scores数组，统计所有分数大于等于threshold的玩家总数，即为答案
  该方案平均时间复杂度为O(n)，仅极端最坏情况会到O(n²)，如果需要稳定最坏时间复杂度，可以采用内置内省排序的nth_element类实现，最坏时间复杂度也能稳定在O(n)。

方案2：计数排序法（适用于分数范围有限场景） #

如果题目约束分数在有限区间内（如0_100、010^4等），可以用计数排序进一步压低时间复杂度：

• 初始化计数数组cnt，下标对应分数，值对应该分数的玩家人数，遍历scores完成计数，耗时O(n)
• 从最高分到最低分遍历cnt数组，累计玩家数，每遇到非0的计数项时排名档次+1，直到排名档次超过k时停止遍历
• 累计的总人数即为答案
  该方案时间复杂度为O(n + M)，其中M为分数的最大取值，只要M没有远大于n，运行效率远高于O(nlogn)的排序方案。

内容的提问来源于stack exchange，提问作者trex1009