如何以O(n)时间复杂度实现有序整数数组的平方排序？

针对这个「将有序整数数组每个元素平方后返回有序数组」的问题，我整理了两种实用解法，分别适配不同的场景需求：

这个解法不需要依赖输入数组的数值范围，适用于所有有序整数数组场景。

思路修正与步骤 #

原思路里提到的「哈希集合」会导致重复元素丢失（比如示例中的-2和2平方都是4，集合会只保留一个），不符合预期输出。正确的步骤应该是：

• 遍历原数组，将每个元素的平方存入一个普通列表
• 对这个列表进行排序，返回排序后的结果

代码示例（Python） #

def sorted_squares(nums):
    # 生成所有元素的平方列表
    squared_nums = [num ** 2 for num in nums]
    # 排序后返回
    squared_nums.sort()
    return squared_nums

# 测试示例输入
print(sorted_squares([-9, -2, 0, 2, 3]))  # 输出: [0, 4, 4, 9, 81]

复杂度分析 #

• 时间复杂度：O(NlogN)，主要来自排序操作（遍历平方是O(N)，可忽略）
• 空间复杂度：O(N)，用于存储平方后的列表（如果允许修改原数组可以优化到O(1)，但一般不推荐）
• 优点：实现简单，无范围限制，通用性强

如果提前知道输入数组的元素范围（比如题目中提到的 -10000 到 10000），可以用这种线性时间的解法，效率更高。

思路 #

• 根据输入范围计算出最大的平方值，创建一个计数数组（或列表）来记录每个平方值出现的次数
• 遍历原数组，统计每个平方值的出现次数
• 从小到大遍历计数数组，将出现过的平方值按次数加入结果列表，自然得到有序数组

代码示例（Python） #

def sorted_squares(nums):
    # 已知输入范围是-10000到10000，最大平方值是10000²
    max_square = 10000 ** 2
    # 创建计数数组，初始值全为0
    count = [0] * (max_square + 1)
    
    # 统计每个平方值的出现次数
    for num in nums:
        square = num ** 2
        count[square] += 1
    
    # 生成有序结果
    result = []
    for square_val in range(max_square + 1):
        if count[square_val] > 0:
            # 按次数添加对应平方值
            result.extend([square_val] * count[square_val])
    return result

# 测试示例输入
print(sorted_squares([-9, -2, 0, 2, 3]))  # 输出: [0, 4, 4, 9, 81]

复杂度分析 #

• 时间复杂度：O(N + M)，其中N是原数组长度，M是最大平方值+1。因为M是固定值（可视为常数），所以整体是O(N)线性时间
• 空间复杂度：O(M + N)，M是计数数组的大小，N是结果数组的大小
• 优点：线性时间效率，比排序解法更快；缺点：依赖输入范围，范围过大时内存开销会很高

内容的提问来源于stack exchange，提问作者J. Doe