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:
1
nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,
2
3
Result: [3, 9, 15, 33]
4
5
nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5
6
7
Result: [-23, -5, 1, 7]
Copied!

2. Implementation

(1) Two Pointers
1
class Solution {
2
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
3
int[] res = new int[nums.length];
4
int index = a >= 0 ? nums.length - 1 : 0;
5
int start = 0, end = nums.length - 1;
6
7
while (start <= end) {
8
int startNum = getNum(nums[start], a, b , c);
9
int endNum = getNum(nums[end], a, b, c);
10
11
if (a >= 0) {
12
if (startNum > endNum) {
13
res[index] = startNum;
14
++start;
15
}
16
else {
17
res[index] = endNum;
18
--end;
19
}
20
--index;
21
}
22
else {
23
if (startNum < endNum) {
24
res[index] = startNum;
25
++start;
26
}
27
else {
28
res[index] = endNum;
29
--end;
30
}
31
++index;
32
}
33
}
34
return res;
35
}
36
37
public int getNum(int x, int a, int b, int c) {
38
return a * x * x + b * x + c;
39
}
40
}
Copied!

3. Time & Space Complexity

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