0360. 有序转化数组 #
- 标签:数组、数学、双指针、排序
- 难度:中等
题目大意 #
给定一个已经排好的整数数组 nums
和整数 a
、b
、c
。
要求:对于数组中的每一个数 x
,计算函数值 $f(x) = ax^2 + bx + c$,请将函数值产生的数组返回。
注意:返回的这个数组必须按照升序排列,并且我们所期望的解法时间复杂度为 $O(n)$。
解题思路 #
这是一道数学题。需要根据一元二次函数的性质来解决问题。因为返回的数组必须按照升序排列,并且期望的解法时间复杂度为 $O(n)$。这就不能先计算再排序了,而是要在线性时间复杂度内考虑问题。
我们先定义一个函数用来计算 f(x)
。然后进行分情况讨论。
- 如果
a == 0
,说明函数是一条直线。则根据b
值的正负来确定数组遍历顺序。- 如果
b >= 0
,说明这条直线是一条递增直线。则按照从头到尾的顺序依次计算函数值,并依次存入答案数组。 - 如果
b < 0
,说明这条直线是一条递减直线。则按照从尾到头的顺序依次计算函数值,并依次存入答案数组。
- 如果
- 如果
a > 0
,说明函数是一条开口向上的抛物线,最小值横坐标为 $diad = \frac{-b}{2.0 * a}$,离 diad 越远,函数值越大。则可以使用双指针从远到近,由大到小依次填入数组。具体步骤如下:- 使用双指针
left
、right
,令left
指向数组第一个元素位置,right
指向数组最后一个元素位置。再定义index = len(nums) - 1
作为答案数组填入顺序的索引值。 - 比较
left - diad
与right - diad
的绝对值大小。大的就是目前距离diad
最远的那个。- 如果
abs(nums[left] - diad)
更大,则将其填入答案数组对应位置,并令left += 1
。 - 如果
abs(nums[right] - diad)
更大,则将其填入答案数组对应位置,并令right -= 1
。 - 令
index -= 1
。
- 如果
- 直到
left == right
,最后将nums[left]
填入答案数组对应位置。
- 使用双指针
- 如果
a < 0
,说明函数是一条开口向下的抛物线,最大值横坐标为 $diad = \frac{-b}{2.0 * a}$,离 diad 越远,函数值越小。则可以使用双指针从远到近,由小到大一次填入数组。具体步骤如下:- 使用双指针
left
、right
,令left
指向数组第一个元素位置,right
指向数组最后一个元素位置。再定义index = 0
作为答案数组填入顺序的索引值。 - 比较
left - diad
与right - diad
的绝对值大小。大的就是目前距离diad
最远的那个。- 如果
abs(nums[left] - diad)
更大,则将其填入答案数组对应位置,并令left += 1
。 - 如果
abs(nums[right] - diad)
更大,则将其填入答案数组对应位置,并令right -= 1
。 - 令
index += 1
。
- 如果
- 直到
left == right
,最后将nums[left]
填入答案数组对应位置。
- 使用双指针
代码 #
|
|