360 Sort Transformed Array

360. Sort Transformed Array

1. Question

Given a sorted array of integersnumsand integer valuesa,bandc. Apply a quadratic function of the form f(x) =ax2+bx+c to each elementxin 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]

2. Implementation

(1) Two Pointers

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] res = new int[nums.length];
        int index = a >= 0 ? nums.length - 1 : 0;
        int start = 0, end = nums.length - 1;

        while (start <= end) {
            int startNum = getNum(nums[start], a, b , c);
            int endNum = getNum(nums[end], a, b, c);

            if (a >= 0) {
                if (startNum > endNum) {
                    res[index] = startNum;
                    ++start;
                }
                else {
                    res[index] = endNum;
                    --end;
                }
                --index;
            }
            else {
                if (startNum < endNum) {
                    res[index] = startNum;
                    ++start;
                }
                else {
                    res[index] = endNum;
                    --end;
                }
                ++index;
            }
        }
        return res;
    }

    public int getNum(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}

3. Time & Space Complexity

Two Pointers: 时间复杂度O(n), 空间复杂度O(n)