算法竞技场EP01：哈希流稳如老狗，二分流帅到飞起，你pick谁？

欢迎来到 「算法竞技场」的直播间！我是你们的主播——老白。今天咱们不聊3A大作，来刷一个经典副本：LeetCode 1331：数组序号转换。（弹幕：大师又在水题！）

别急别急，这副本看似新手村教学，但里面藏着一个专门坑害萌新的超时诅咒。今天的解说，我就带大家看看三位玩家分别是怎么挑战的——有人开场就被秒，有人无伤通关，还有人秀得BOSS头皮发麻。

任务简报

给你一个数组 arr，把每个元素替换成它排序后的名次。
规则：数字越大名次越大，相同数字名次相同，名次从1开始，且尽可能小。

案例怪物：[40, 10, 20, 30]
排序去重后的实力榜：[10, 20, 30, 40] → 名次 [1, 2, 3, 4]
输出：[4, 1, 2, 3]

一号选手·暴力一行流

好的，一位萌新选手率先冲了上去！他掏出了一卷极其华丽的代码卷轴！

return [sorted(set(arr)).index(i) + 1 for i in arr]

观众们，一行流，极简美学！——但是，画面卡住了！加载圆圈转个不停，然后一个巨大的 TLE 砸在屏幕上，直接把萌新选手送回了复活点。

（弹幕：帅不过三秒哈哈哈） （弹幕：经典超时，我上次这么死还是在上次） （弹幕：老师：我不是说一行不好，但你这一行里藏了个O(n²)的炸弹）

导播，麻烦给个慢镜头：

• sorted(set(arr)) 放在列表推导式里，每次循环都重新排列整个怪物图鉴！
• .index(i) 又是从图鉴第一个开始挨个点名，线性大海捞针。

这就好比你在副本里，每砍一只小怪，都要把整个地图的怪物重新清点一遍，再从地图入口跑到它面前确认位置。时间复杂度爆炸成 O(n² log n)——BOSS还没见到呢，先把自己跑死了。

结论：这卷轴是诅咒道具，捡到请直接销毁。

二号选手·哈希圣光

接下来上场的是经验丰富的老玩家。他抬手就是一个 哈希映射·圣光护符！

def arrayRankTransform(arr: List[int]) -> List[int]:
    sorted_unique = sorted(set(arr))               			# 一次排序，世界清净
    rank_map = {v:i for i,v in enumerate(sorted_unique,1)}  # 人手一张名次卡
    return [rank_map[v] for v in arr]              			# 瞬移贴标签，德芙都没我丝滑

观众们，看这波操作！ 他先花 O(n log n) 的代价，一次性把怪物实力榜排好，给每个怪物发了名次卡片。然后拿着卡片直接 O(1) 瞬移贴标签，全程没有被诅咒摸到一下，完美通关！

数据面板：

• 排序耗时 O(n log n) （一次性投资，终身受益）
• 建表耗时：O(n) （给每个怪物发身份证）
• 查表总耗时 O(n) （O(1)查询就是爽）
• 总伤害 O(n log n)，BOSS直接融化，AC到手。

（弹幕：教练我想学这个） （弹幕：学会了，这就去和面试官对线，让他知道什么叫专业） （弹幕：哈希表YYDS！字典才是真神！）

这一套连招，逻辑清晰、性能拉满、面试官最爱，拿到任何场上都稳如老狗。

三号选手·二分飞刀

最后登场的，是职业选手的操作秀——他从怀里掏出了一柄寒光闪闪的 二分飞刀！

from bisect import bisect_left

def arrayRankTransform(arr: List[int]) -> List[int]:
    sorted_unique = sorted(set(arr))
    # 咻咻咻，二分飞刀连斩
    return [bisect_left(sorted_unique, val) + 1 for val in arr]

看这飞刀轨迹！——bisect_left 在有序列表里用折半查找，每次定位都是 O(log n)，砍掉一半搜索空间！虽然单次没圣光 O(1) 快，但这飞刀是C语言淬炼过的，常数因子极小，整套连招如德芙般纵享丝滑。

同样 O(n log n) 的DPS，但职业选手就是偏爱这种肌肉记忆般的微操。当你需要反复在同一个有序列表里搜索时，这招就是你的本命飞刀。

（弹幕：帅是一辈子的事）
（弹幕：不会二分不配叫玩家） （弹幕：面试的时候用这招，面试官眼睛都亮了）

伤害统计 & 出装推荐

（弹幕：哈希：你负责帅，我负责赢，分工明确！） （弹幕：大师，能把第一行代码从我大脑里删除吗？这玩意儿有毒！） （弹幕：我选第四种：CV大法，复制粘贴永不过时） （弹幕：学到了学到了，这就去刷十道题巩固一下）

老白的出装推荐（敲黑板！）

• 打排位上分/面试对线，请用 哈希圣光，朴实无华且枯燥地赢。（面试官：“你的代码风格很稳健啊。"）
• 匹配局想秀/Code Review装逼，掏出 二分飞刀，把击杀镜头录下来发集锦。（同事：“卧槽，你这代码有点东西啊！"）
• 至于那个一行流卷轴……放仓库角落当纪念吧，提醒自己：不是所有一行代码都叫优雅。

好了，今天的「算法竞技场」直播就到这里！觉得过瘾的把 666 打在公屏上！（虽然我看不到哈哈哈）。我是老白，要继续去下个副本浪了，咱们野区再见！

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。