企业官网建设流程全解析

1. 题目解析与核心思路

LeetCode 3379题"转换数组"是一个典型的数组操作问题，主要考察对数组元素变换的理解和实现能力。题目要求我们根据特定规则对输入数组进行转换，最终输出符合条件的结果数组。

1.1 题目要求详解

题目给定一个整数数组nums，我们需要对每个元素nums[i]执行以下操作：

1. 找到数组中比nums[i]小的所有元素
2. 计算这些元素的个数
3. 用这个计数替换原来的nums[i]值

例如，对于输入数组[8,1,2,2,3]，转换过程如下：

• 对于8，有4个元素比它小(1,2,2,3)→替换为4
• 对于1，有0个元素比它小→替换为0
• 对于2，有1个元素比它小(1)→替换为1
• 对于3，有3个元素比它小(1,2,2)→替换为3 最终输出结果为[4,0,1,1,3]

1.2 暴力解法分析

最直观的解法是使用双重循环：

def smallerNumbersThanCurrent(nums): result = [] for i in range(len(nums)): count = 0 for j in range(len(nums)): if nums[j] < nums[i]: count += 1 result.append(count) return result

这种方法时间复杂度为O(n²)，对于小规模数据可行，但当数组长度较大时（如n>10000），性能会明显下降。

2. 优化解法探索

2.1 排序+哈希表法

更高效的解法是先排序数组，然后利用哈希表记录每个元素的排名：

def smallerNumbersThanCurrent(nums): sorted_nums = sorted(nums) rank_dict = {} for i, num in enumerate(sorted_nums): if num not in rank_dict: rank_dict[num] = i return [rank_dict[num] for num in nums]

这个解法的时间复杂度主要来自排序的O(n log n)，后续操作都是O(n)，整体性能显著优于暴力解法。

注意：当数组中有重复元素时，哈希表会记录第一次出现的位置，这正是我们需要的比当前元素小的元素个数。

2.2 计数排序优化

对于元素范围有限的情况（如题目说明元素值在0到100之间），可以使用计数排序进一步优化：

def smallerNumbersThanCurrent(nums): count = [0] * 101 # 题目说明元素值在0-100之间 for num in nums: count[num] += 1 # 计算前缀和 for i in range(1, 101): count[i] += count[i-1] return [count[num-1] if num > 0 else 0 for num in nums]

这种方法时间复杂度为O(n)，是最高效的解决方案，特别适合元素值范围已知且不大的情况。

3. 不同语言实现对比

3.1 Java实现

class Solution { public int[] smallerNumbersThanCurrent(int[] nums) { int[] count = new int[101]; for (int num : nums) { count[num]++; } for (int i = 1; i < 101; i++) { count[i] += count[i-1]; } int[] result = new int[nums.length]; for (int i = 0; i < nums.length; i++) { result[i] = nums[i] == 0 ? 0 : count[nums[i]-1]; } return result; } }

3.2 C++实现

class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { vector<int> count(101, 0); for (int num : nums) { count[num]++; } for (int i = 1; i < 101; i++) { count[i] += count[i-1]; } vector<int> result; for (int num : nums) { result.push_back(num == 0 ? 0 : count[num-1]); } return result; } };

3.3 JavaScript实现

var smallerNumbersThanCurrent = function(nums) { const count = new Array(101).fill(0); nums.forEach(num => count[num]++); for (let i = 1; i < 101; i++) { count[i] += count[i-1]; } return nums.map(num => num === 0 ? 0 : count[num-1]); };

4. 复杂度分析与比较

提示：在实际面试中，建议先提出暴力解法，然后逐步优化，展示你的思考过程。

5. 边界条件与测试用例

5.1 常见边界情况

1. 空数组输入：应该返回空数组
2. 所有元素相同：[5,5,5]→[0,0,0]
3. 元素全部为0：[0,0,0]→[0,0,0]
4. 元素全部相同且不为0：[3,3,3]→[0,0,0]
5. 已排序数组：[1,2,3,4]→[0,1,2,3]
6. 逆序数组：[4,3,2,1]→[3,2,1,0]

5.2 测试用例示例

test_cases = [ ([8,1,2,2,3], [4,0,1,1,3]), ([6,5,4,8], [2,1,0,3]), ([7,7,7,7], [0,0,0,0]), ([], []), ([0,0], [0,0]), ([1,2,3,4,5], [0,1,2,3,4]) ] for nums, expected in test_cases: result = smallerNumbersThanCurrent(nums) assert result == expected, f"Failed for {nums}, got {result}, expected {expected}" print("All test cases passed!")

6. 实际应用场景

这类数组转换问题在实际开发中有多种应用场景：

1. 数据标准化：将原始数据转换为基于排名的相对值
2. 推荐系统：计算用户评分相对于其他用户的排名
3. 统计分析：确定数据点在数据集中的百分位
4. 成绩排名：计算学生成绩在班级中的排名情况

例如，在电商系统中，我们可能需要计算某个商品价格相对于同类商品的便宜程度排名，就可以使用类似的算法。

7. 常见错误与调试技巧

7.1 常见错误

1. 忽略重复元素：没有正确处理重复元素会导致排名计算错误
2. 边界条件处理不当：特别是当元素为0时，容易忘记特殊处理
3. 空间分配不足：在使用计数排序时，数组大小需要根据元素范围确定
4. 时间复杂度估计错误：误认为排序解法比暴力解法更差

7.2 调试技巧

1. 打印中间结果：在排序后和建立哈希表后打印结果，验证是否正确
2. 小规模测试：先用小数组测试，确保基本逻辑正确
3. 边界测试：专门测试空数组、全相同元素等边界情况
4. 性能分析：对于大规模数据，使用时间测量函数验证算法效率

import time def test_performance(): large_nums = [random.randint(0, 100) for _ in range(100000)] start = time.time() smallerNumbersThanCurrent(large_nums) print(f"Time taken: {time.time()-start:.4f} seconds") test_performance()

8. 算法扩展与变种

8.1 类似题目推荐

1. LeetCode 1365. 有多少小于当前数字的数字（本题的原始版本）
2. LeetCode 1122. 数组的相对排序（扩展了排序和比较的概念）
3. LeetCode 1051. 高度检查器（涉及排序和位置比较）
4. LeetCode 1636. 按照频率将数组升序排序（结合了计数和排序）

8.2 变种问题思考

1. 如果要求计算大于当前元素的个数，如何修改算法？
2. 如果要求同时计算小于和大于当前元素的个数，如何高效实现？
3. 如果数组包含浮点数，算法需要做哪些调整？
4. 如果数组非常大（无法一次性装入内存），如何设计外部排序方案？

对于第一个变种问题，解决方案可以是：

def largerNumbersThanCurrent(nums): sorted_nums = sorted(nums, reverse=True) rank_dict = {} for i, num in enumerate(sorted_nums): if num not in rank_dict: rank_dict[num] = i return [rank_dict[num] for num in nums]

这个解法通过反向排序，然后记录排名来实现计算大于当前元素的个数。

9. 个人实战经验分享

在实际解决这个问题时，我总结了以下几点经验：

1. 先理解后编码：一定要先完全理解题目要求，可以手动计算几个例子验证理解是否正确。我曾经因为没注意"小于"而不是"小于等于"而浪费了调试时间。

2. 从简单开始：先实现暴力解法，确保理解正确，再考虑优化。不要一开始就追求最优解。

3. 利用题目条件：本题说明元素范围在0-100之间，这个提示强烈暗示可以使用计数排序。在面试中要注意题目给出的所有信息。

4. 测试要充分：特别是边界情况，如全相同元素、包含0的元素等。我曾经因为没测试空数组情况而在周赛中失分。

5. 空间换时间：计数排序虽然需要额外空间，但能获得线性时间复杂度，这在算法竞赛中往往是更优的选择。

对于想要进一步提高的同学，我建议：

1. 尝试用不同的方法实现同一个问题，比较它们的性能差异
2. 在LeetCode上查看讨论区，学习其他人的优秀解法
3. 自己设计测试用例，包括各种边界情况
4. 尝试解决该问题的变种，如前面提到的扩展问题

最后，记住算法能力的提升是一个渐进的过程，坚持每天解决一个问题，几个月后你会有明显的进步。这道"转换数组"题目虽然看似简单，但包含了数组操作、排序、哈希表等多个基础知识点，是很好的练习素材。