arrays - 排序结果数组

Question

我在 Adob​​e 面试中被问到这个问题:

我们有一个按升序排序的整数数组。我们还有 3 个整数 A、B 和 C。我们需要为数组中的每个元素 x 应用 A*x*x + B*x + C 并返回相应的排序数组。

给我的例子:

Input array = -1 0 1 2 3 4
A = -1, B = 2, C = -1`

将公式应用于每个元素的结果 = -4 -1 0 -1 -4 -9
所以预期结果 = -9 -4 -4 -1 -1 0(已排序)

我最好的解决方案是应用公式并对它进行排序，得到 O(nlogn) 解决方案。我做得再好不过了。

任何改进它的指导都是有帮助的。

Answer 1

给出的方程是parabolic .因此，将其应用于已排序数组的结果将生成一个数组，该数组将具有最大值/最小值，其左右子数组已排序。

在您的情况下，最大值为 0，其左侧的子数组 [-4 -1] 按升序排序，其右侧的子数组[-1 -4 -9] 降序排列。

您需要做的就是合并这些排序的数组，这在时间上是线性的。

所以算法是:

1. 对每个元素应用等式
2. 找到最大值/最小值
3. 合并子数组