难度: Medium
Submission
运行时间: 24 ms
内存: 16.8 MB
class Solution:
def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
i, j = 0, len(nums) - 1
res = [0] * len(nums)
p = j
while i <= j:
left = a * (nums[i] ** 2) + b * nums[i] + c
right = a * (nums[j] ** 2) + b * nums[j] + c
if a > 0:
if left >= right:
res[p] = left
i += 1
else:
res[p] = right
j -= 1
else:
if left <= right:
res[len(nums) - 1 - p] = left
i += 1
else:
res[len(nums) - 1 - p] = right
j -= 1
p -= 1
return res
Explain
该题解的思路基于抛物线的性质。给定的函数 f(x) = ax² + bx + c 形成一个抛物线。当 a > 0 时，抛物线开口向上，最大值在两端；当 a < 0 时，抛物线开口向下，最小值在两端。基于此性质，可以从数组的两端开始比较，选择合适的值填充到结果数组中。如果 a > 0，从数组的最后向前填充结果数组；如果 a < 0，则从数组的开始向后填充。这种方法利用了有序数组的特性，减少了不必要的计算。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
i, j = 0, len(nums) - 1 # 初始化两个指针，分别指向数组的开始和结束
res = [0] * len(nums) # 创建结果数组
p = j # p 指针用于从结果数组的末尾开始填充
while i <= j: # 当左指针不超过右指针时循环
left = a * (nums[i] ** 2) + b * nums[i] + c # 计算左端点的抛物线值
right = a * (nums[j] ** 2) + b * nums[j] + c # 计算右端点的抛物线值
if a > 0: # 如果 a > 0，抛物线开口向上
if left >= right: # 选择较大的值填充到 res[p]
res[p] = left
i += 1 # 移动左指针
else:
res[p] = right
j -= 1 # 移动右指针
else: # 如果 a < 0，抛物线开口向下
if left <= right: # 选择较小的值填充到 res[len(nums) - 1 - p]
res[len(nums) - 1 - p] = left
i += 1 # 移动左指针
else:
res[len(nums) - 1 - p] = right
j -= 1 # 移动右指针
p -= 1 # 更新 p 指针
return res # 返回结果数组
Explore
抛物线的性质决定了其最值的位置。对于给定的抛物线函数 f(x) = ax² + bx + c，其顶点的 x 坐标由公式 -b/(2a) 给出。当 a > 0 时，抛物线开口向上，其两端值逐渐增大，因而最大值出现在左端或右端；当 a < 0 时，抛物线开口向下，其两端值逐渐减小，因而最小值出现在左端或右端。由于题目中的数组是有序的，这意味着可以直接通过比较数组端点的函数值来确定填充顺序，实现高效的排序。
当 a = 0 时，函数 f(x) = ax² + bx + c 简化为 f(x) = bx + c，这是一个线性函数。在这种情况下，若 b > 0，则函数值随 x 增大而增大；若 b < 0，则函数值随 x 增大而减小。因此，可以简单地按照 b 的符号来决定填充结果数组的顺序：如果 b >= 0，从数组的开始向后填充；如果 b < 0，则从数组的末尾向前填充。这保持了算法的一致性和高效性。
当抛物线开口向上（a > 0）时，函数值在数组的两端较高，且随着 x 值向中间靠拢而减小。因此，为了建立一个从大到小的有序数组，需要从结果数组的末尾开始填充较大的值。这样，可以确保在比较两端的函数值时，总是将较大的值放在结果数组的后端，然后逐步向数组的前端移动，从而保持数组的有序性。