1. 先搞清楚“比自己强的人数”到底在问什么1.1 从赛题描述到可计算的模型前两天在某个在线评测平台上刷题看到一道分值200分的题目题面写得非常简短“给定一个整数序列对于序列中的每个元素请统计序列中有多少个数严格大于它。”语言限制是Java、JavaScript、Python三选一。当年第一次遇到这类题的时候我脑子里冒出来的第一个念头是这题不是O(N²)直接双重循环就完事了吗但等我真正把数据范围看清楚才发现这个200分一点都不白给。先把这个题翻译成人话。假设现在有5个人的得分分别是[90, 85, 90, 70, 100]那么对于第一个人90分比他强的人就是得分严格大于90的人这里只有100这一个所以答案是1对于第三个人同样也是90分比他强的还是只有100答案也是1没有人比自己强这里的“比自己强”必须是严格大于也就是说相同分数的两个人互相不算“比自己强”这是题目里最容易忽略的隐含条件。输出的时候需要按原序列的顺序依次输出每个人的“更强人数”例如上面的例子输出就是1 2 1 4 0。我把这道题当作一个典型的“排名统计”问题来理解因为在实际业务里这个场景实在太常见了游戏服务器要算每个玩家在全区里的战力排名赛事系统要算每支队伍在小组中的胜场排名甚至一些社交产品里“你超过了多少好友”的文案背后也是同一套计算逻辑。把这个题吃透并不只是为了拿那200分而是为了掌握一类统计问题的基础切入点。1.2 样例推演严格大于与相等的处理为了把边界条件彻底弄清楚我习惯先用手工推演一个小例子。假如序列是[90, 85, 90, 70]把它按降序排好就是[90, 90, 85, 70]。逐个来看。对于第一个90降序序列里从头开始扫描第一个严格大于90的元素不存在所以更强人数是0。对于85降序序列里严格大于85的元素是前面两个90所以是2。对于70前面三个元素90、90、85都大于70所以是3。整个答案就是[0, 2, 0, 3]。这里有两个教训第一两个90的存在感完全不同它们都不比对方“强”所以在统计时要保证相等分数不会被计入“更强人数”第二降序排序只是方便我们利用有序性做二分查找而不是简单地输出下标。很多同学第一次写这题直接把分数降序排序后对每个元素输出它在排序数组里的下标这是错的——遇到重复值的时候下标会把那些和自己同分的人也当成“比你强”的人。严谨的模型是对于每个元素x它的答案等于“所有严格大于x的元素个数”在降序数组中这个值恰好等于“第一个小于等于x的元素的下标”。为什么因为降序数组里下标0到k-1这一段元素全都严格大于x而k位置开始就不再大于x了所以k就是我们要的计数。1.3 数据范围决定了你能用什么算法做算法题第一件事不是写代码而是看数据范围。这道200分的题N最大可以到10⁵级别值域则可能去到10⁹级别的随机整数。如果不是这个范围我可能真会推荐你直接暴力对于每个元素 x 遍历整个数组统计大于 x 的个数时间复杂度O(N²)N10⁵时就是10¹⁰次比较跑完需要几分钟甚至更久评测机不可能给你这种复杂度通过。N1000以内倒是完全没问题但既然分值给了200分出题人显然是想考核“排序二分”这类O(N log N)的思路或者进一步考核树状数组离散化这类O(N log N)但扩展性更强的做法。所以在动手之前先把范围看清楚这决定了你后面所有的实现细节。2. 暴力解与排序二分两条路线的推导2.1 为什么暴力会挂掉我不止一次见过有人在这个题上交暴力代码理由也很朴素“统计比自己大的数不是一眼就能看出来的嘛两层循环嘛。”对于小范围的数据比如N100、值域不超过1000暴力不仅能过而且代码好写好调。但问题在于这类题出现在200分的档位数据几乎一定会卡O(N²)。暴力代码大概长这样def brute(arr): n len(arr) res [] for i in range(n): cnt 0 for j in range(n): if arr[j] arr[i]: cnt 1 res.append(cnt) return res它的问题在于大量重复计算。对于每个元素它都把整个数组重新扫一遍而这些扫描之间没有任何信息复用。比如你已经知道85前面有两个90那在统计70的时候其实可以直接复用“有多少人大于85”再加上“有多少人介于70和85之间”的信息但暴力解把这些信息全都扔掉了。我倾向于把暴力解当作一个“正确性基准”来使用。写正解之前先写一个暴力版本用小数据对照验证这样可以在调试时快速排查排序、二分里是不是写错了。2.2 排序后“比自己强”就是“第一个小于等于出现的位置”主解法的核心观察是当你把所有分数按降序排好后每个元素在有序数组中的位置已经隐含了所有统计信息。设降序数组为sorted_arr那么“严格大于x”的人数等于sorted_arr中小于等于x的第一个位置的下标值。举个例子会更直观。还是[90, 85, 90, 70]降序后是[90, 90, 85, 70]。我要统计85的答案二分找到第一个小于等于85的位置从左往右扫描90大于8590大于8585不大于85所以这个位置是2答案就是2。再统计70找到第一个小于等于70的位置是3答案就是3。为什么“第一个小于等于”这个位置刚好就是答案因为降序数组中位置0到pos-1的元素都严格大于x它们恰好就是“比自己强的人”。而位置pos以及之后的所有元素都不再大于x不能再算进去。所以答案等于pos不是pos1也不是pos-1。这里有一个很多初学者会犯的经典错误直接用二分查找模板在排序数组里找一个恰好等于x的位置然后返回这个位置的下标这在有重复值时会出现偏差因为第一个等于x的位置往往不是第一个小于等于x的位置。处理的关键在于二分查找的判定条件。我常用的模板是lo 0, hi n while lo hi: mid (lo hi) // 2 if sorted_arr[mid] x: lo mid 1 else: hi mid 答案 lo这个循环结束时lo指向的位置满足它左边全是严格大于x的元素它自己以及右边全是小于等于x的元素于是lo就是答案。这个模板是基于“寻找第一个小于等于x的位置”来写的一开始容易搞反我建议你把它背下来然后多手推两个有重复值的例子验证。2.3 复杂度对比排序的时间复杂度是O(N log N)二分查找每个元素是O(log N)N个元素总共O(N log N)整体就是O(N log N)。空间上需要一个排序后的副本数组O(N)。对比暴力的O(N²)当N10⁵时O(N²)要执行约5×10⁹次内层操作而O(N log N)大概是1.7×10⁶次操作差距是三个数量级。这也是为什么所有像样的算法课程都会反复强调排序的价值排序一次后面所有查询都能享受对数级别的快速查找。本质上这题就是在考“如何预处理数据来支持多次查询”。3. 三种语言的AC实现与输入输出细节3.1 Java版包装类排序与手写二分Java的排序API有一个让很多人抓狂的细节对基本类型数组int[]进行降序排序不能直接传Collections.reverseOrder()因为这个比较器只能作用于对象数组。所以你有两条路要么把int[]转成Integer[]再排序要么干脆升序排序后从尾部往前二分。实测下来我更喜欢手写二分的方案因为Arrays.binarySearch在重复元素和降序数组上的行为并不直观容易踩坑。下面这个版本是我在OJ上调通的import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); Integer[] arr new Integer[n]; for (int i 0; i n; i) { arr[i] sc.nextInt(); } Integer[] sorted arr.clone(); Arrays.sort(sorted, (a, b) - b - a); // 降序 StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { int x arr[i]; int lo 0, hi n; while (lo hi) { int mid (lo hi) 1; if (sorted[mid] x) { lo mid 1; } else { hi mid; } } if (i 0) sb.append( ); sb.append(lo); } System.out.println(sb); } }注意几个细节。第一(lo hi) 1是为了防止当lo hi溢出变成负数在数组长度很大的时候这个写法更安全。第二排序用的lambda表达式(a, b) - b - a在数据范围很大会有溢出风险比如b是10⁹、a是-10⁹时b - a会溢出成负数导致排序异常。更稳妥的写法是(a, b) - Integer.compare(b, a)。第三用StringBuilder拼接输出而不是逐次System.out.print是为了避免大量IO操作拖慢运行速度实测在N10⁵时这个优化能省不少时间。3.2 Python版读入技巧与列表推导Python写这类题最大的优势是代码短最大的坑是输入输出格式和排序默认行为。看一个能直接提交的版本import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) if not data: return n data[0] arr data[1:1 n] sorted_arr sorted(arr, reverseTrue) res [] for x in arr: lo, hi 0, n while lo hi: mid (lo hi) // 2 if sorted_arr[mid] x: lo mid 1 else: hi mid res.append(str(lo)) sys.stdout.write( .join(res)) if __name__ __main__: main()sys.stdin.buffer.read().split()是我推荐的读入姿势。它一次性把整个标准输入读进来按空白字符切分比逐行input()快很多在N10⁵时差异很明显。这里我还想多说一句Python的列表推导式虽然优雅但在这个二分循环里强行用推导式反而会把逻辑绕晕不如老老实实写for循环可读性优先。如果你用Python的bisect模块也不是不行但要小心方向问题。bisect_right(sorted_arr, x)在降序数组上是没法直接使用的因为bisect系列默认升序语义你传降序数组进去会得到很奇怪的结果。我试过把数组存成负数升序然后用bisect_right那又是另一种绕法。既然手写二分只有四五行我更建议直接手写逻辑透明不容易记错。3.3 JavaScript版sort默认字典序是个深坑JavaScript版是三种语言里最容易出“灵异事件”的罪魁祸首就是Array.prototype.sort()。我之前在一道题里写过arr.sort()然后惊喜地发现[10, 9, 100, 2]被排成了[10, 100, 2, 9]当时整个人都懵了。查了文档才想起来JS的sort默认把元素转成字符串后按字典序排序数字比较必须显式传比较器。正确写法是const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; rl.on(line, line lines.push(line.trim())); rl.on(close, () { const data lines.join( ).split(/\s/).map(Number); const n data[0]; const arr data.slice(1, 1 n); const sorted [...arr].sort((a, b) b - a); const res arr.map(x { let lo 0, hi n; while (lo hi) { const mid Math.floor((lo hi) / 2); if (sorted[mid] x) lo mid 1; else hi mid; } return lo; }); console.log(res.join( )); });输入处理上我先把所有行收集起来再统一切分是因为竞赛环境里数据可能分布在多行按行逐行处理容易漏掉跨行的数组元素。const sorted [...arr].sort(...)是为了不修改原数组因为后面统计时还需要原顺序。这里Math.floor((lo hi) / 2)和Java的1作用一样防止整数溢出JS虽然数字都是浮点但位运算会转成32位整数所以用Math.floor更直观。我还想给JS版一个建议如果N很大回调函数里的比较器会被调用很多次性能敏感时可以先用Uint32Array之类的类型化数组但一般OJ环境用普通数组就够了不必过度优化。真正要注意的是把map、join这些数组操作用好因为它们比显式for循环更容易保证不越界。4. 树状数组与离散化从“静态统计”到“动态维护”4.1 什么时候才需要树状数组排序二分解法的局限性在于它要求所有数据一次性给出而且查询过程是静态的不能在处理过程中动态插入新的人。如果题目改成“每次加入一个分数立即查询当前有多少人比自己强”排序二分就变得很别扭因为每次插入都要重新排序复杂度退化到O(N² log N)。这时候就需要一种支持动态插入和动态查询的数据结构树状数组就是最常见的方案。另外排序二分的答案依赖原数组的完整结果无法在数据流场景下边接收边输出。所以在一些变种题里即使N不大用树状数组也会让代码的扩展性更好。我通常会在脑子里做一个决策只有查询就用排序二分有动态插入或者需要在线处理就用树状数组。4.2 离散化压缩值域树状数组的索引是整数但分数可能是10⁹级别的不可能直接开一个10⁹大小的数组。离散化的思路是把“具体的分数”映射成“这个分数在所有不同分数中的排名”。假设分数是[90, 85, 90, 70, 100]不同分数排序后是[70, 85, 90, 100]那么70映射为185映射为290映射为3100映射为4。压缩之后值域大小M最多等于N空间就变成了O(N)。离散化的代码很简单vals sorted(set(arr)) rank {v: i 1 for i, v in enumerate(vals)}4.3 倒序插入的代码与推导树状数组统计“比自己强的人数”等价于统计“已插入元素中严格大于当前元素的个数”。如果从右往左遍历原数组那么在处理arr[i]时已经插入的恰好是原数组中所有在它右侧的元素。右侧元素中严格大于它的个数就等于“已插入总数减去已插入元素中小于等于它的个数”。实现时树状数组的每个位置维护某个离散化值出现的次数“小于等于某个值的个数”就是树状数组的前缀和。完整代码class BIT: def __init__(self, n): self.n n self.tree [0] * (n 1) def add(self, idx, val): while idx self.n: self.tree[idx] val idx idx -idx def sum(self, idx): s 0 while idx 0: s self.tree[idx] idx - idx -idx return s def stronger_count(arr): vals sorted(set(arr)) rank {v: i 1 for i, v in enumerate(vals)} bit BIT(len(vals)) res [0] * len(arr) total 0 for i in range(len(arr) - 1, -1, -1): r rank[arr[i]] res[i] total - bit.sum(r) # 已经插入的右侧元素里严格大于当前值的个数 bit.add(r, 1) total 1 return res为什么total - bit.sum(r)算出来的是严格大于而不是大于等于因为bit.sum(r)统计的是离散化后排名不大于r的所有已插入元素的数量也就是所有小于等于当前分数的右侧元素数量。用已插入总数减去它剩下的就是严格大于当前分数的右侧元素数量。这个逻辑链需要你亲手推一遍重复值的情况两个90分先后被处理先处理的右边那个90先插入后处理的左边那个90在查询时已插入的右边90虽然和它同分但因为同分的90也落在bit.sum(r)里所以不会被算进“更强人数”正好符合题意。树状数组单次插入和查询都是O(log M)M是不同分数的个数整体复杂度O(N log N)。虽然和排序二分复杂度同阶但它支持在任意时刻插入新元素这是静态排序方案做不到的。如果你在面试里被追问“如果数据是流式的怎么办”能接出这个解法是一个明显的加分项。5. 实测踩坑清单与三道题通用经验5.1 典型错误一把小于等于算成了小于这个错误最隐蔽。有人在二分时把判定条件写成if (sorted[mid] x) lo mid 1; else hi mid;意思是寻找“第一个小于x的位置”。对于没有重复值的用例这两种写法答案一样因为不存在等于x的元素。一旦出现重复值比如[90, 85, 90, 70]后一个90就会被统计成有1个比自己强的人——其实是左边那个90这就错了。我在本地用小数据测试时因为输入样例没有重复值第一次提交都AC了后来自己补了重复值测试才发现这个隐患。建议是在本地准备一个专门的“重复值暴力对拍脚本”生成随机小数组暴力计算标准答案和你的正解输出对比。对拍几次这种边界问题基本都能暴露。5.2 典型错误二二分边界差一个二分的边界是另一个高频翻车点。我看过有人把hi初始化为n - 1然后循环条件写lo hi结果所有元素都大于目标值时答案总会少1有人把mid (lo hi) // 2的更新逻辑写对称导致死循环。正确的模板是左闭右开区间[0, n)循环不变量是“答案在[lo, hi)内”这样初始化lo 0, hi n最安全。如果你不想依赖这个模板也可以用一种更“傻瓜”的方式先用java.util.Arrays.binarySearch一类API找插入点但我劝你别这么干。手写二分的模板最多5行背下来比记忆API在各种边界情况下的行为可靠得多。我自己的习惯是把这套“寻找第一个不满足某条件的位置”的模板抄在笔记本上遇到类似题直接套。5.3 典型错误三JS的sort与Java基本类型排序JS的sort默认字典序我已经说过了。Java的Arrays.sort(int[])倒是不会字典序但它默认升序你想降序又不能直接传比较器。很多同学在Java里试图写Arrays.sort(sorted, Collections.reverseOrder())结果编译报错因为Collections.reverseOrder()只能用于对象数组。解决方案是改用Integer[]或者索性升序排序后在二分里做镜像处理。我还见过一个Java的坑Integer.compare(a, b)和a - b的区别。在Arrays.sort(Integer[], Comparator)里用b - a做比较器当b是Integer.MIN_VALUE、a是Integer.MAX_VALUE时会溢出导致排序结果错误。不要偷懒Comparator里一律用Integer.compare或Comparator.reverseOrder()。5.4 刷题策略如何在200分题里练出300分的能力这类题的价值不在AC本身而在于一题多想。我把这道题按难度分了三个层次第一层能想到排序二分并写出来第二层能处理重复值、大值域、三种语言差异等各种边界第三层能迁移到树状数组和离散化甚至在面试场景里讲清楚“为什么不用暴力”。一个我常用的练习方法是AC之后强制自己用另一种数据结构重写一遍。比如这题先用排序二分写一遍再用树状数组写一遍最后把两种解法放到本地数据生成器上做性能对比。经过这样一轮下次再遇到“统计右侧有多少元素大于当前值”“逆序对个数”这些经典变种题时你会发现自己对有序性和数据结构之间关联的敏感度明显提高了。还有一个实用技巧输出格式永远用“空格分隔、末尾不补空格”的规范来拼串。评测系统对行末空格的处理各有不同有的会报Presentation Error虽然不影响判据但会白白浪费一次提交。用StringBuilder拼串或者join是最稳妥的。最后说点实际的体会。在OJ上一道200分的题往往意味着“给你20分钟想出思路、40分钟写对代码”。我第一次做类似的统计题时光在二分边界上调了半小时后来发现其实就是把写成了。从那以后我给自己定了个规矩写完任何二分先用重复值最小的数据跑一遍再跑一个所有值相等的数据比如[5,5,5,5]预期输出应该是0 0 0 0。这一条简单的自测习惯帮我省下了无数次的错误提交。如果你也正在刷题建议把这道题当作一个起点认真把它彻底吃透因为你后面会遇到的所有“逆序对”“排名统计”“右侧大数数量”类题目核心骨骼都是从这里长出来的。