> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/two_sum/sort-transformed-array.md).

# 360. Sort Transformed Array

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]
```

## Thoughts

排好序的数组问对每个数做ax^2 + bx + c后结果的排序。二次方的抛物线分为开头向上和向下。 用两个指针分别指向首尾，当开头向上意味着两端要比中心大，从后往前插入结果，插谁取决于两个指针代表的数谁大；开头向下类似，方向倒过来。

## Code

```python
class Solution:
    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
        def cal(x):
            return a * x ** 2 + b * x + c
        i, j, res = 0, len(nums) - 1, []
        while i <= j:
            p, q = cal(nums[i]), cal(nums[j])
            if p > q and a > 0 or p < q and a <= 0:
                i += 1
                res.append(p)
            else: 
                j -= 1
                res.append(q)
        if a > 0: res.reverse()
        return res
        
```

```java
class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] res = new int[nums.length];
        int l = 0, r = nums.length - 1;
        int index = a > 0 ? nums.length - 1 : 0;
        while (l <= r) {
            int left = quad(nums[l], a, b, c), right = quad(nums[r], a, b, c);
            if (a > 0) {
                if (left > right) {
                    res[index--] = left;
                    l++;
                } else {
                    res[index--] = right;
                    r--;
                }
            } else {
                if (left < right) {
                    res[index++] = left;
                    l++;
                } else {
                    res[index++] = right;
                    r--;
                }
            }
        }
        return res;
    }

    private int quad(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}
```

## Analysis

时间复杂度O(N).