Description

Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic function of the form f(x) = ax² + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)**

Example:

nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,

Result: [3, 9, 15, 33]

nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5

Result: [-23, -5, 1, 7]

Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.

Solution

Two-pointer, O(n), S(1)

二次函数的函数图还记得么？

image.png

所以说方程结果是有规律可寻的。对于a >= 0的情况，越往两端值越大。对于a <= 0的情况，越往两端值越小。由于input已经是sorted的了，我们可以用two-pointer法，直接向sorted[]中填结果即可。a >= 0是从大往小填，a < 0是从小往大填。

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] sorted = new int[n];
        int left = 0;
        int right = n - 1;
        int index = a >= 0 ? n - 1 : 0;
        
        while (left <= right) {
            if (a >= 0) {
                sorted[index--] = func(nums[left], a, b, c) >= func(nums[right], a, b, c)
                    ? func(nums[left++], a, b, c) : func(nums[right--], a, b, c);
            } else {
                sorted[index++] = func(nums[left], a, b, c) >= func(nums[right], a, b, c)
                    ? func(nums[right--], a, b, c) : func(nums[left++], a, b, c);
            }
        }
        
        return sorted;
    }
    
    private int func(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}