LeetCode 1365：三种解法吃透“小于当前数字”的复杂度思维

今天刷题时我在LeetCode热门100题单里碰到了这道1365. 有多少小于当前数字的数字。题面很短难度也不高但我提交完看了一下自己的计时耗时100秒——从读题到写出能过的代码差不多就是这个时间。本来想直接跳过写下一题后来一想这道题其实非常值得拆开聊一聊因为它同时具备三种典型解法暴力、排序加哈希、计数排序刚好能串起刷题最基础也最重要的一套复杂度思维。如果你正在刷LeetCode简单题或者刚入门算法题想把“会做一道题”升级成“会做一类题”那么这篇题解应该对你有用。我不打算只贴一个最优解而是把这道题从最笨的办法到最优的做法全部拆开讲清楚每一步的思考过程、代码写法和边界坑。1. 先从“耗时100”聊起这道题的真实诉求和样例拆解1.1 题目到底在问什么题目描述很直白给你一个数组nums对于每个nums[i]请你统计数组中一共有多少个元素严格小于nums[i]然后返回同样长度的结果数组。看官方示例输入nums [8,1,2,2,3] 输出[4,0,1,1,3]解释一下对于8数组里小于 8 的数字有 1、2、2、3一共 4 个所以结果第一个位置是 4对于1没有比 1 更小的数字所以是 0第一个2比它小的只有 1所以是 1第二个2同样只有 1 比它小所以结果还是 1对于3比它小的有 1、2、2共 3 个。注意这里的关键词是“严格小于”。也就是说两个相同的2之间互相不算只有一个1同时在它们前面。这个细节决定了后面排序解法的写法如果你没注意到很容易在重复元素上翻车。1.2 为什么这是一道经典的“入门复杂度”题我在刷题群里经常看到有人问这道题有什么好讲的不就是两轮循环统计一下吗确实暴力解法能过因为题目给的数据范围很宽松2 nums.length 10000 nums[i] 100。n最大只有 1000O(n^2)最坏也就是一百万次操作现代计算机跑起来毫无压力。但正因为数据范围小很多人才会忽略题目背后真正想考察的点。LeetCode 把这道题放进热门100题单不只是让你体验“AC 的快感”更希望你能通过它理解同一个需求在不同约束下可以用完全不同的思路去做复杂度的差别可以是数量级的。这道题恰好就是复杂度分析的绝佳样本。从O(n^2)到O(n log n)再到O(n k)三个方案对应三种思维层次。我下面会把三条路都走一遍顺便说说各自适合什么场景。2. 暴力双循环为什么在最坏1e6的规模下依然能过2.1 先写出最直白的版本面对任何题目我习惯先把最暴力的方案写出来不是为了提交而是为了确认自己对题意的理解没有偏差。它的逻辑简单到不用过脑子对每个nums[i]再遍历一遍整个数组nums[j]只要nums[j] nums[i]计数器加一。class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) - List[int]: n len(nums) res [] for i in range(n): cnt 0 for j in range(n): if nums[j] nums[i]: cnt 1 res.append(cnt) return res这个代码简单到有点朴素。你甚至不需要额外的空间时间复杂度是O(n^2)空间复杂度是O(1)不考虑返回数组的话。2.2 “耗时100”里的真实体验标题里的“耗时100”指的是我第一次做这道题时从读题到写出这个暴力解法再提交差不多用了 100 秒。为什么敢说这个数字因为我当时的做题流程是打开题目看样例锁定“严格小于”这个坑直接写双循环提交通过看了眼时间。说实话这道题用暴力解法一次过的概率非常高。1000个元素的双循环只有10^6次比较在 LeetCode 的评测环境下耗时约在几毫秒到十几毫秒之间完全不会超时。所以很多人觉得这道题“这么简单也配进热门100”从求解角度看确实简单但它真正的价值在于引导你思考效率问题。2.3 暴力解法什么时候能选这里我分享一个很实用的判断方法看到题目先看数据范围。n 1000O(n^2)大概10^6随便写n 10^5O(n^2)是10^10绝对超时至少要O(n log n)n 10^7甚至更大要奔着O(n)或O(n log n)去设计。这个“数量级直觉”是刷题的基本功。如果你在面试里写出暴力解面试官大概率会追问“能不能优化”这时候你如果不能立刻接上更优解法会很被动。所以暴力解只适合用来验证思路不适合作为最终答案。3. 排序加哈希用“位置”替代“比较”的经典套路3.1 思路转变排序之后“小于”就变成了“位置”暴力解法重复比了O(n^2)次这些比较大多数是冗余的。如果先把数组排好序问题就变得非常直观在一个升序数组中某个数字左边有几个元素就有几个小于它的数字。比如[1,2,2,3,8]排好序之后1左边没有元素所以它小于其他数字的个数是 0第一个2左边只有1所以是 1第二个2左边还是只有1结果也是 13左边有 1、2、2共 3 个8左边有 1、2、2、3共 4 个。所以核心就变成排序后每个数字第一次出现的位置索引就是小于它的元素个数。3.2 代码实现为什么要记录“第一次出现位置”这里就是前面说的重复元素陷阱。数组中如果有重复值排序后相同数字会连续出现。拿第二个2来说它的索引虽然是 2但小于它的元素数量应该和第一个2一样都是索引 0 左边的元素个数也就是 1。所以不能简单记录每个元素在排序后的当前位置而要记录每个值第一次出现的位置。我用一个哈希表遍历排序后的数组只把第一次出现的num存进字典class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) - List[int]: sorted_nums sorted(nums) pos {} for i, num in enumerate(sorted_nums): if num not in pos: pos[num] i return [pos[num] for num in nums]这段代码里pos[num]存的永远是某个数字第一次出现的位置。比如pos[2]在排序数组中的第一个2的地方值是 1而不是第二个2的位置 2。这样2的答案就是 1完全符合“严格小于”的语义。3.3 复杂度分析和适用场景排序的时间复杂度是O(n log n)哈希表存储要O(n)空间整体跑下来比暴力快得多。在n 1000的数据下你可能感觉不到和暴力的差异但如果把n放大到10^5排序解法依然能轻松过暴力解法就会直接超时。这个解法的通用性很好。它不需要依赖题目中“数值范围有限”这一限制即使nums[i]的范围冲到10^9也能处理。所以当你第一时间没有发现计数排序这个更优思路时排序哈希是面试中最稳的回答。我个人觉得这道题最值得记住的不是代码本身而是那个转换排序能把“比较大小”变成“看位置先后”。这个套路在很多中等题里都会反复出现比如求每个元素右侧比它小的元素数量、离线查询子数组中的第 K 小等等。4. 计数排序数据范围只有100时的最优答案4.1 题目里藏着的“数字范围提示”很多人刷题只看n的范围忽略了nums[i]的取值范围。这道题给了0 nums[i] 100意味着数组中每个元素的值只在 0 到 100 之间一共 101 种可能。面对这种“值域很小”的题目计数排序几乎是条件反射级别的最优解。思路很简单用一个长度为 101 的数组cnt统计每个数字出现的频率对cnt求前缀和cnt[x]重新定义为“小于等于 x 的元素个数”对于原始数组中的num答案就是cnt[num - 1]当 num 大于 0 时如果 num 等于 0答案直接是 0。4.2 前缀和与边界处理的细节我写一个完整版本class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) - List[int]: cnt [0] * 101 for num in nums: cnt[num] 1 # 前缀和cnt[i] 表示 i 的元素个数 for i in range(1, 101): cnt[i] cnt[i - 1] res [] for num in nums: if num 0: res.append(0) else: res.append(cnt[num - 1]) return res先说前缀和这一步。原始cnt[num]是频率比如nums [1,2,2,3]初始cnt[1]1, cnt[2]2, cnt[3]1。做前缀和后cnt[2]变成 4表示数组里小于等于 2 的元素一共有 4 个1 和两个 2 和某个小于等于2的反正就是一个累计。那么“严格小于 2”的元素个数就是小于等于 1 的个数也就是cnt[1]即cnt[num - 1]。这个过程不需要排序也不需要哈希表。你只要对每个num查询cnt[num-1]就行了。4.3 这个解法的最优性计数排序的时间复杂度是O(n k)其中k是数值范围这里k 101可以近似看成O(n)。空间复杂度是O(k)也就是固定大小的常数空间。相比排序解法它把O(n log n)降到了线性级别在数据量大的时候优势非常明显。但要注意计数排序不是万能的。如果题目改成0 nums[i] 10^9你还开一个 10 亿长度的数组吗显然不现实。所以最优解法一定要基于题目给的数据范围来判断。我在实际练习中踩过一个相关的小坑直接把cnt长度设成max(nums) 1忘了 0 也要占一个位置。当nums里的最大值是 100 时长度需要是 101 而不是 100。另外如果题目出现负数计数数组还需要做索引偏移比如把每个值加一个偏移量否则下标会越界。这道题没有负数所以最省心。5. 三种解法放一起比复杂度、代码量和适用边界为了看得更清楚我把三种解法整理成一张表解法时间复杂度空间复杂度代码量适用场景暴力双循环O(n^2)O(1)最少n 1000验证思路排序 哈希O(n log n)O(n)中等通用性强适合面试回答计数排序O(n k)O(k)中等值域有限且较小时最优这里k是数值范围。本题目中k101可以当常数看待。如果你只追求提交通过暴力解最省事如果你想在面试里展示算法素养至少应该写出排序哈希如果面试官进一步追问“还能不能再快”计数排序就是这道题的终局答案。我在刷题时有一个明显体会很多人拿到题直接开始写最优解反而容易卡在边界条件上。更平滑的路径是先暴力再优化最后总结复杂度。这样你不仅能 AC还能给面试官讲清楚每一步的取舍理由。面试官想听的往往不是你背下来的最优解而是你如何从暴力出发发现问题中的约束条件逐步推导出更高效的方案。另外提一个写代码的小习惯在 LeetCode 上提交前先在本地把示例和几个自己构造的边界测一遍。比如nums [0, 0, 0]预期结果是[0, 0, 0]nums [1, 2, 3, 4]预期是[0, 1, 2, 3]nums [4, 3, 2, 1]结果应该还是[3, 2, 1, 0]因为结果只跟值有关和原数组顺序无关。这些测试能帮你快速暴露“0 要不要特殊处理”这类边界问题。6. 从1365顺藤摸瓜相关题目与刷题心法6.1 “小于当前数字”问题族的通用框架做完 1365你会发现有一整类题目都在问“某个元素和它左边/右边其他元素的关系”。这类题的常见套路就这么几种一是排序加二分。如果题目只问“小于某个特定值的元素个数”不需要修改原数组可以先排序原数组或副本然后对每个查询用bisect_left找左边界。二是频次数组加前缀和。当值域较小且固定计数排序是最自然的思路能兼顾时间和空间。三是树状数组/线段树。当题目需要动态更新或统计逆序对时比如“计算右侧小于当前元素的个数”这种经典题简单的前缀和就不够用了需要借助树状数组维护动态排名。1365 属于最简单的一层但它把上面三种思路的雏形都埋了。你可以把它当成理解“排序位置映射”和“值域频次统计”的入门题。6.2 几道可以连着刷的题目我顺着这道题往外扩展推荐三道题数组序号转换这道题同样用到排序哈希映射把数组中的值映射成 1 到 n 的序号计算右侧小于当前元素的个数算是 1365 的加强版不再要求“严格小于自己”而是只统计右侧比自己小的元素数量需要用到树状数组或归并排序两个数组的交集 II虽然本质是哈希表统计频率但如果你先想到排序双指针也能跟这里的“排序后位置关系”联系起来。我还想提一个热词里出现的题目——LeetCode 994 腐烂的橘子。它和 1365 看起来毫不相干一个是多源 BFS一个是简单统计但它们都在热门100题单里。这其实提醒了我们刷题不能只盯着一类题猛刷广度也很重要。简单题用来练基本功中等题用来建立模型难题用来突破思维边界。6.3 从“耗时100”到“稳定秒杀”的学习节奏回到标题里的“耗时100”。100 秒对一个已经刷过不少题的人来说其实不算快因为这道题应该能做到 30 秒读完题、20 秒确定思路、10 秒写完代码。但没关系我反正不追求高速刷题我更在意的是做一道题有没有把这三种复杂度都过一遍。我建议你也用类似的学习节奏拿到一道简单题先只靠直觉写暴力然后强迫自己至少想出第二种解法再打开题解看有没有更优的做法。这个过程比单纯 AC 十道题有价值得多。等你把 1365 吃透之后再遇到类似“有多少小于当前数字的数字”这种描述第一反应就不会只是双循环了。最后再分享一个小技巧把sorted(nums)和原nums分开处理时一定要记住返回的结果必须保持原数组的顺序所以最后一步要用原数组的数据去查表而不是直接用排序后的数组。这个小细节我在初学排序解法的时候栽过一次希望你别再踩第二遍。