arrays - 在排序数组上应用函数

Question

摘自谷歌面试问题here

假设您有一个排序的整数数组(正数或负数)。您想要对数组的每个元素 x 应用 f(x) = a * x^2 + b * x + c 形式的函数，以使结果数组仍然排序。用 Java 或 C++ 实现它。输入是初始排序数组和函数参数(a、b 和 c)。

您认为我们可以在不到 O(n log(n)) 的时间内完成它，其中 n 是数组大小(例如，对数组的每个元素应用一个函数，然后对数组进行排序)？

Answer 1

我认为这可以在线性时间内完成。因为该函数是二次函数，所以它会形成一条抛物线，即值下降(假设“a”为正值)下降到某个最小点，然后会增加。因此，算法应该迭代排序的值，直到我们到达/通过函数的最小值点(可以通过简单的微分来确定)，然后对于最小值之后的每个值，它应该向后遍历较早的值以寻找插入该值的正确位置。使用链接列表将允许项目就地移动。