企业官网建设流程全解析

今天刷题时，我在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 <= 1000，0 <= nums[i] <= 100。n最大只有 1000，O(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 <= 1000：O(n^2)大概10^6，随便写；
• n <= 10^5：O(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，结果也是 1；
• 3左边有 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 种可能。面对这种“值域很小”的题目，计数排序几乎是条件反射级别的最优解。

思路很简单：

1. 用一个长度为 101 的数组cnt统计每个数字出现的频率；
2. 对cnt求前缀和，cnt[x]重新定义为“小于等于 x 的元素个数”；
3. 对于原始数组中的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. 三种解法放一起比：复杂度、代码量和适用边界

为了看得更清楚，我把三种解法整理成一张表：

这里k是数值范围。本题目中k=101，可以当常数看待。如果你只追求提交通过，暴力解最省事；如果你想在面试里展示算法素养，至少应该写出排序+哈希；如果面试官进一步追问“还能不能再快”，计数排序就是这道题的终局答案。

我在刷题时有一个明显体会：很多人拿到题直接开始写最优解，反而容易卡在边界条件上。更平滑的路径是：先暴力，再优化，最后总结复杂度。这样你不仅能 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 几道可以连着刷的题目

我顺着这道题往外扩展，推荐三道题：

• 1331. 数组序号转换：这道题同样用到排序+哈希映射，把数组中的值映射成 1 到 n 的序号；
• 315. 计算右侧小于当前元素的个数：算是 1365 的加强版，不再要求“严格小于自己”，而是只统计右侧比自己小的元素数量，需要用到树状数组或归并排序；
• 350. 两个数组的交集 II：虽然本质是哈希表统计频率，但如果你先想到排序双指针，也能跟这里的“排序后位置关系”联系起来。

我还想提一个热词里出现的题目——LeetCode 994 腐烂的橘子。它和 1365 看起来毫不相干，一个是多源 BFS，一个是简单统计，但它们都在热门100题单里。这其实提醒了我们：刷题不能只盯着一类题猛刷，广度也很重要。简单题用来练基本功，中等题用来建立模型，难题用来突破思维边界。

6.3 从“耗时100”到“稳定秒杀”的学习节奏

回到标题里的“耗时100”。100 秒对一个已经刷过不少题的人来说，其实不算快，因为这道题应该能做到 30 秒读完题、20 秒确定思路、10 秒写完代码。但没关系，我反正不追求高速刷题，我更在意的是做一道题有没有把这三种复杂度都过一遍。

我建议你也用类似的学习节奏：拿到一道简单题，先只靠直觉写暴力，然后强迫自己至少想出第二种解法，再打开题解看有没有更优的做法。这个过程比单纯 AC 十道题有价值得多。等你把 1365 吃透之后，再遇到类似“有多少小于当前数字的数字”这种描述，第一反应就不会只是双循环了。

最后再分享一个小技巧：把sorted(nums)和原nums分开处理时，一定要记住返回的结果必须保持原数组的顺序，所以最后一步要用原数组的数据去查表，而不是直接用排序后的数组。这个小细节我在初学排序解法的时候栽过一次，希望你别再踩第二遍。