如何以非降序O（N）时间复杂度对已经排序的数组进行排序？

Question

问题：

以非降序给出排序后的数组，也以非降序返回每个数字的平方数组。例如：[-4，-2，-1,0,3,5]-> [0,1,4,9,16,25]

我正在尝试两点方法。比较两个极值的绝对值，然后将其添加到新列表中。这是代码：

def make_square(arr):
    if arr == []:
        return Null
    left = 0
    right = len(arr)-1
    result = len(arr) * [None]
    result_ind = len(result)-1

    while left < right:
        if abs(arr[left]) > abs(arr[right]):
            result[result_ind] = (arr[left])**2
            left +=1
        else:
            result[result_ind] = (arr[right])**2
            right -=1
        result_ind -=1
    return result

make_square([-4,-2,-1,0,3,5])

但是，我得到以下结果：

[无，1、4、9、16、25]

我该如何解决？

Answer 1

您可以简单地做到这一点：

def make_square(arr):
    return sorted([a**2 for a in arr])

print(make_square([-4,-2,-1,0,3,5]))

输出：
[0, 1, 4, 9, 16, 25]

Answer 2

def make_square(arr):
if arr == []:
    return Null
left = 0
right = len(arr)-1
result = len(arr) * [None]
print(result)
result_ind = len(result)-1

while left <= right:           #You missed the starting case where left is equal to right
    if abs(arr[left]) > abs(arr[right]):
        result[result_ind] = (arr[left])**2
        left +=1
    else:
        result[result_ind] = (arr[right])**2
        right -=1
    result_ind -=1
return result

make_square([-4,-2,-1,0,3,5])

Answer 3

[使用Python中一些较少使用的功能，可以使它非常简短：显式的list_iterator，用于遍历输入，双端队列和heapq.merge。

from heapq import merge
from collections import deque


def make_square(arr):
    itr = iter(arr)
    neg = deque()
    for x in itr:
        if x >= 0:
            break
        neg.appendleft(x**2)

    return list(merge(neg, [x**2], (x**2 for x in itr)))

我们只使用for循环，并对其进行重复的符号检查，直到看到第一个非负值。直到我们做完，我们
prepend每个输入值的平方保持双端队列以保持正方形不递减。 （在列表之前）效率低得多。）
[merge需要三个可迭代项：
负值的预先计算的平方，以非降序排列
包含第一个非负输入值的平方的单例列表
生成其余输入值平方的发生器
并以非降序返回平方的可迭代数。
（理想情况下，我们可以在脱离循环之前将x推回itr，但是我们不能这样做，而且解决方法没有比将第三个参数简单地传递给merge更好的方法。 ）