360. Sort Transformed Array

Given asortedarray of integersnumsand integer valuesa,bandc. Apply a function of the form f(x) =ax^2+bx+c to each elementxin the array.

The returned array must be insorted 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]

S： two pointer O(n)

因为有x^2而数组内都是整数，所以transform后的结果要么从两边往中间越来越小（a > 0时），要么从两边往中间越来越大（a < 0时）

    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int n = nums.size();
        vector<int> result(n);
        if (n == 0) return result;
        int left = 0, right = n - 1;
        if (a >= 0) {
            int idx = n - 1;
            while (left <= right) {
                int leftValue = a * nums[left] * nums[left] + b * nums[left] + c;
                int rightValue = a * nums[right] * nums[right] + b * nums[right] + c;
                if (leftValue >= rightValue) {
                    result[idx--] = leftValue;
                    left++;
                } else {
                    result[idx--] = rightValue;
                    right--;
                }
            }
        } else {
            int idx = 0;
            while (left <= right) {
                int leftValue = a * nums[left] * nums[left] + b * nums[left] + c;
                int rightValue = a * nums[right] * nums[right] + b * nums[right] + c;
                if (leftValue <= rightValue) {
                    result[idx++] = leftValue;
                    left++;
                } else {
                    result[idx++] = rightValue;
                    right--;
                }
            }
        }
        return result;
    }