algorithm - 在 O(n) 的列表中对数字平方进行排序？

Question

给定一个按排序顺序排列的整数列表，例如，[-9, -2, 0, 2, 3]，我们必须对每个元素进行平方并按排序顺序返回结果。因此，输出将是:[0, 4, 4, 9, 81]。

我可以想出两种方法:

1. O(NlogN) 方法 - 我们将每个元素的平方插入哈希集中。然后将元素复制到列表中，排序后返回。

2. O(n) 方法 - 如果输入元素有界限(比如 -100 到 -100)，那么我们创建一个大小为 20000 的 bool 列表(用于存储 - 10000 到 10000)。对于每个输入元素，我们将相应的平方数标记为真。例如，对于输入中的 9，我会将 bool 数组中的 81 标记为 true。然后遍历这个 bool 列表，将所有为真的元素插入到一个返回列表中。请注意，在此我们做了一个假设 - 输入元素存在界限。

有没有什么方法可以在 O(n) 时间内完成，甚至无需为输入假设任何边界？

Answer 1

好吧，我可以想到一个O(n) 的方法

1. 将输入分成 2 个列表。一个带有负数的列表，我们称此列表为 A。和一个带有正数和 0 的列表 B。这是在保留输入顺序的同时完成的，这是微不足道的:O(n)
2. 反向列表A。我们这样做是因为一旦平方，如果翻转元素之间的关系大于
3. 对两个列表中的每一项进行平方:O(n)
4. 运行merge 操作，与合并排序的操作类似。 : O(n)
5. 总计:O(n)

完成:)