如何根据另一数组的值为数组分配排名？最优实现方案

给定第一个数组 points 为 arrayOf(22, 8, 17, 13, 20)，需要生成第二个数组，规则是：最大值对应排名1，第二大值对应排名2，以此类推，最终结果为 (1, 5, 3, 4, 2)。求最优实现方式。

核心思路 #

要生成正确的排名数组，关键是保留元素原始索引的同时按值排序，再将排名映射回原数组位置。这种方式的时间复杂度为O(n log n)（由排序操作主导），是基于比较的排序类问题的最优复杂度，空间复杂度为O(n)，属于合理开销。

代码实现（Kotlin） #

针对无重复元素的场景，代码如下：

val points = arrayOf(22, 8, 17, 13, 20)
val result = IntArray(points.size)

// 将元素与原始索引配对，按值降序排序
val sortedWithIndex = points.withIndex()
    .sortedByDescending { it.value }

// 遍历排序后的列表，给原位置分配排名
sortedWithIndex.forEachIndexed { rank, entry ->
    result[entry.index] = rank + 1 // 排名从1开始计数
}

println(result.contentToString()) // 输出：[1, 5, 3, 4, 2]

扩展：处理重复元素 #

如果数组存在重复值（如两个元素值相同应共享同一排名），可调整代码如下：

val points = arrayOf(22, 22, 17, 13, 20)
val result = IntArray(points.size)

val sortedWithIndex = points.withIndex()
    .sortedByDescending { it.value }

var currentRank = 1
result[sortedWithIndex[0].index] = currentRank

for (i in 1 until sortedWithIndex.size) {
    val prevEntry = sortedWithIndex[i-1]
    val currEntry = sortedWithIndex[i]
    // 当前元素值与前一个不同时，更新排名为当前位置+1
    if (currEntry.value != prevEntry.value) {
        currentRank = i + 1
    }
    result[currEntry.index] = currentRank
}

println(result.contentToString()) // 输出：[1, 1, 3, 5, 2]

为什么这是最优解 #

• 时间效率：排序操作的时间复杂度为O(n log n)，这是基于比较的排序算法的理论下界，无法进一步优化；其余步骤均为O(n)线性操作，整体效率最高。
• 空间效率：仅需存储带索引的排序列表和结果数组，空间开销为O(n)，在大多数场景下都可接受。
• 可读性与可维护性：代码逻辑清晰，步骤明确，易于理解和扩展（如处理重复值）。

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