初始化预定义大小数组在有序数组平方排序问题中的优势探讨

题目要求 #

编写一个函数，输入非空的升序整数数组，返回一个长度相同的新数组，其中元素为原数组元素的平方，且同样按升序排列。

我的解法 #

def sortedSquaredArray(array):
    sml = 0
    lrg = len(array)-1
    res = []
    while len(res) != len(array):
        if abs(array[sml]) < abs(array[lrg]):
            res.append(array[lrg]**2)
            lrg -= 1
        else:
            res.append(array[sml]**2)
            sml +=1
    res.reverse()       
    return res

平台提供的解法 #

def sortedSquaredArray(array):
    res = [0 for _ in array]
    sml = 0
    lrg = len(array)-1
    
    for idx in reversed(range(len(array))):
        smallerValue = array[sml]
        largerValue = array[lrg]
        
        if abs(smallerValue) > abs(largerValue):
            res[idx] = smallerValue * smallerValue
            sml += 1
        else:
            res[idx] = largerValue * largerValue
            lrg -=1

    return res

疑问与解答 #

我认为两种解法的时间复杂度和空间复杂度均为O(n)。想了解平台采用预定义大小数组的做法是否有优势？我猜测可能提升了代码可读性，且无需像我一样反转数组，但reverse()的时间复杂度也是O(n)，应该不会对算法产生显著影响，对吗？

两种解法确实都是**O(n)**时间、**O(n)**空间的最优解，核心思路均为双指针从数组两端向中间遍历，通过绝对值比较确定平方值的顺序。平台解法的预定义数组做法有几个实际优势：

• 避免额外反转操作：虽然reverse()是O(n)复杂度，但实际运行时需要遍历数组交换元素，多了一次内存操作；预定义数组直接从后往前填充，省去了这一步额外遍历。
• 内存分配更高效：Python中列表append()操作虽为均摊O(1)，但当容量不足时会触发扩容（通常是翻倍），带来额外的内存分配和数据拷贝；预定义大小的数组一开始就分配了足够内存，避免了扩容开销。
• 代码逻辑更直观：通过索引直接定位填充位置，逻辑贴合“从大到小确定平方值，放到结果对应位置”的思路，无需后续反转，代码意图更清晰。

不过从算法复杂度的角度，两种解法没有本质区别，都是合格的最优解，面试中写出任意一种都能体现对双指针思路的掌握。

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