Sort Transformed Array

Given a sorted array of integers nums and integer values a, b and c. Apply a 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:

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]

Tips:

用two pointers做非常容易，但是要注意 a >=0 和a < 0两种情况，输入到result的时候顺序得变，之后两个得到的数的判定情况也得变。

Code:

public class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] result = new int[nums.length];
        if (nums == null || nums.length == 0) {
            return result;
        }
        int left = 0, right = nums.length - 1;
        int i = a >= 0 ? nums.length - 1 : 0;
        while(left <= right) {
            int l = a * nums[left] * nums[left] + b * nums[left] + c;
            int r = a * nums[right] * nums[right] + b * nums[right] + c;
            if (a >= 0) {
                if (l <= r) {
                    result[i--] = r;
                    right--;
                } else {
                    result[i--] = l;
                    left++;
                }                
            } else {
                if (l > r) {
                    result[i++] = r;
                    right--;
                } else {
                    result[i++] = l;
                    left++;
                } 
            }
        }
        return result;
    }
}