LeetCode第360题_有序转化数组

技术文档

LeetCode 第360题：有序转化数组

📖 文章摘要

本文详细解析LeetCode第360题\"有序转化数组\"，这是一道数学和双指针问题。文章提供了基于双指针的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升数学思维和双指针技巧的读者。

核心知识点： 双指针、数学分析、抛物线、排序
难度等级： 中等
推荐人群： 具有一定算法基础，想要提升数学问题解决能力的程序员

题目描述

给你一个已经排好序的整数数组 nums 和整数 a、b、c。对于数组中的每一个数 x，计算函数值 f(x) = ax^2 + bx + c，请将函数值也按照升序排序。

示例

示例 1：

输入：nums = [-4,-2,2,4], a = 1, b = 3, c = 5输出：[3,9,15,33]解释：函数值 f(x) = x^2 + 3x + 5

示例 2：

输入：nums = [-4,-2,2,4], a = -1, b = 3, c = 5输出：[-23,-5,1,7]解释：函数值 f(x) = -x^2 + 3x + 5

提示

1 <= nums.length <= 200
-100 <= nums[i] <= 100
-100 <= a, b, c <= 100
nums 已按升序排序

解题思路

本题可以使用双指针方法解决：

根据a的正负确定函数值的单调性
使用双指针从两端向中间移动
根据单调性选择较大或较小的值
将结果存入新数组

时间复杂度： O(n)
空间复杂度： O(n)

图解思路

函数分析表

a的符号函数特性处理策略 a > 0 开口向上两端值较大 a < 0 开口向下两端值较小 a = 0 线性函数根据b的符号决定

双指针移动表

情况左指针右指针选择 a > 0 增大减小较大值 a < 0 增大减小较小值

代码实现

C# 实现

public class Solution { public int[] SortTransformedArray(int[] nums, int a, int b, int c) { int n = nums.Length; int[] result = new int[n]; int left = 0, right = n - 1; int index = a >= 0 ? n - 1 : 0; while (left <= right) { int leftVal = Calculate(nums[left], a, b, c); int rightVal = Calculate(nums[right], a, b, c); if (a >= 0) { if (leftVal >= rightVal) {  result[index--] = leftVal;  left++; } else {  result[index--] = rightVal;  right--; } } else { if (leftVal <= rightVal) {  result[index++] = leftVal;  left++; } else {  result[index++] = rightVal;  right--; } } } return result; } private int Calculate(int x, int a, int b, int c) { return a * x * x + b * x + c; }}

Python 实现

class Solution: def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]: n = len(nums) result = [0] * n left, right = 0, n - 1 index = n - 1 if a >= 0 else 0 while left <= right: left_val = self.calculate(nums[left], a, b, c) right_val = self.calculate(nums[right], a, b, c) if a >= 0: if left_val >= right_val:  result[index] = left_val  left += 1 else:  result[index] = right_val  right -= 1 index -= 1 else: if left_val <= right_val:  result[index] = left_val  left += 1 else:  result[index] = right_val  right -= 1 index += 1 return result def calculate(self, x: int, a: int, b: int, c: int) -> int: return a * x * x + b * x + c

C++ 实现

class Solution {public: vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) { int n = nums.size(); vector<int> result(n); int left = 0, right = n - 1; int index = a >= 0 ? n - 1 : 0; while (left <= right) { int leftVal = calculate(nums[left], a, b, c); int rightVal = calculate(nums[right], a, b, c); if (a >= 0) { if (leftVal >= rightVal) {  result[index--] = leftVal;  left++; } else {  result[index--] = rightVal;  right--; } } else { if (leftVal <= rightVal) {  result[index++] = leftVal;  left++; } else {  result[index++] = rightVal;  right--; } } } return result; } private: int calculate(int x, int a, int b, int c) { return a * x * x + b * x + c; }};

执行结果

C# 实现

执行用时：156 ms
内存消耗：45.2 MB

Python 实现

执行用时：32 ms
内存消耗：16.4 MB

C++ 实现

执行用时：0 ms
内存消耗：7.2 MB

性能对比

语言执行用时内存消耗特点 C++ 0 ms 7.2 MB 执行效率最高，内存占用最小 Python 32 ms 16.4 MB 代码简洁，易于理解 C# 156 ms 45.2 MB 类型安全，内存占用较大

代码亮点

🎯 使用双指针高效处理
💡 根据a的符号确定处理策略
🔍 处理边界情况和特殊情况
🎨 代码结构清晰，易于维护

常见错误分析

🚫 未考虑a=0的特殊情况
🚫 双指针移动方向错误
🚫 结果数组索引计算错误
🚫 整数溢出问题

解法对比

解法时间复杂度空间复杂度优点缺点双指针 O(n) O(n) 高效，实现简单需要额外空间排序 O(n log n) O(n) 直观，易于理解效率较低

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第360题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

LeetCode第360题_有序转化数组