Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic function of the form f(x) = ax2 + bx + c to each element x in the array.
The returned array must be in sorted order.
Expected time complexity: O(n)
Example 1:
Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]
Example 2:
Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]
class Solution(object):
def sortTransformedArray(self, nums, a, b, c):
"""
:type nums: List[int]
:type a: int
:type b: int
:type c: int
:rtype: List[int]
"""
return sorted(map(lambda x: a * x ** 2 + b * x + c, nums))
从代码看，排序的时间复杂度似乎是O(nlogn),但其实是O(n)级别的。为什么呢？
- 题目中给出的array是有序的
- array经过一元二次方程处理。
- 由我们初中的知识可以知道，一元二次方程在坐标轴上可分为
上升区间和下降区间，python会自动识别出这两个区间，并采用Timsort来合并成有序数组。所以时间复杂度为O(n)
（TimSort 是 Python 中 list.sort 的默认实现）。该算法找到数据中已经排好序的块-分区，每一个分区叫一个run，然后按规则合并这些run。排序的输入的单位不是一个个单独的数字，而是一个个的块-分区。其中每一个分区叫一个run。针对这些 run 序列，每次拿一个 run 出来按规则进行合并。每次合并会将两个 run合并成一个 run。合并的结果保存到栈中。合并直到消耗掉所有的 run，这时将栈上剩余的 run合并到只剩一个 run 为止。这时这个仅剩的 run 便是排好序的结果。