360. 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:

1
2
3
4
5
6
7
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]

解法1： Two pointers + Math

如果a是正数，那么在边缘的x所对应的数字是最大的，而最小值在中间。
如果a是负数，那么在边缘的x所对应的数字是最小的，最大值在中间。
可以改变要写入的位置来精简代码。

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] res = new int[n];
        int i = 0, j = n - 1;
        int index = a >= 0 ? n - 1 : 0;
        while (i <= j) {
            int left = calc(nums[i], a, b, c);
            int right = calc(nums[j], a, b, c);
            if (a >= 0) {
                if (left >= right) {
                    res[index--] = left;
                    i++;
                } else {
                    res[index--] = right;
                    j--;
                }
            } else {
                if (left >= right) {
                    res[index++] = right;
                    j--;
                } else {
                    res[index++] = left;
                    i++;
                }
            }
        }
        return res;        
    }
    private int calc(int num, int a, int b, int c) {
        return a * num * num + b * num + c;
    }
}