360. Sort Transformed Array (Medium) Google

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

Solution 1: Math + Two Pointers O(n); O(1)

the problem seems to have many cases a>0, a=0,a<0, (when a=0, b>0, b<0). However, they can be combined into just 2 cases: a>0 or a<0

1.a>0, two ends in original array are bigger than center if you learned middle school math before.

2.a<0, center is bigger than two ends.

so use two pointers i, j and do a merge-sort like process. depending on sign of a, you may want to start from the beginning or end of the transformed array.

For a==0 case, it does not matter what b’s sign is. The function is monotonically increasing or decreasing. you can start with either beginning or end.

    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] res = new int[n];
        int l = 0, r = n - 1;
        int i = a > 0 ? n - 1 : 0;
        while (l <= r) {
            int left = quad(nums[l], a, b, c);
            int right = quad(nums[r], a, b, c);
            if (a > 0) {
                if (left >= right) {
                    res[i--] = left; // 因为index--，所以先填大的value
                    l++;
                } else {
                    res[i--] = right;
                    r--;
                }
            } else {
                if (left >= right) {
                    res[i++] = right; // 因为index++，所以先填小的value

                    r--;
                } else {
                    res[i++] = left;
                    l++;
                }
            }
        }
        return res;
    }

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

简单版：对sorted array的数字平方后排序

    public static int[] sortSquaredSortedArray(int[] nums) {
        int i = 0, j = nums.length - 1, index = j;
        int[] result = new int[nums.length];
        while (i <= j) {
            if (nums[i] * nums[i] >= nums[j] * nums[j]) result[index--] = nums[i] * nums[i++];
            else result[index--] = nums[j] * nums[j--];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {-4,-1,0,1,3,4,5};
        System.out.println(Arrays.toString(sortSquaredSortedArray(nums)));
    }