LeetCode 977：有序数组的平方解法复杂度对比及最优解询问

你的解法复杂度拆解 #

你用map()生成平方数组，再通过sorted()排序最后转成IntArray的解法：

• 时间复杂度：map()遍历数组是O(n)，但Kotlin的sorted()基于TimSort实现，时间复杂度为O(n log n)，所以整体时间复杂度是O(n log n)。
• 空间复杂度：map()、sorted()以及最终转IntArray都需要创建和原数组长度线性相关的额外空间，整体为O(n)。

双指针解法复杂度拆解 #

那个标注O(n)的双指针解法，核心是利用原数组非递减的特性——绝对值最大的元素必然在数组两端。用左右指针从两端向中间遍历，比较平方值大小后从结果数组末尾开始填充：

• 时间复杂度：仅需一次遍历处理所有元素，每个元素只访问一次，所以是O(n)，时间效率明显优于你的解法。
• 空间复杂度：需要创建一个和原数组长度相同的结果数组，没有额外的线性空间开销，所以也是O(n)，和你的解法空间复杂度一致。

有没有更优解？ #

从复杂度角度看，双指针解法已经是这个问题的最优解：

• 时间上不可能比O(n)更优，因为至少要遍历每个元素一次计算平方值，这是问题的最低时间门槛。
• 空间上，如果允许修改原数组，尝试原地修改的话，平方后的元素顺序会混乱，后续原地排序又会回到O(n log n)的时间，反而不如双指针解法；如果要求返回新数组，O(n)的空间是必须的——毕竟要存储n个结果元素，没法再压缩。

所以双指针解法就是当前问题的最优选择，它和你的解法空间复杂度相同，但时间效率更高。

内容的提问来源于stack exchange，提问作者Compose Learner