Description#
Given a sorted integer array nums and three integers a, b and c, apply a quadratic function of the form f(x) = ax2 + bx + c to each element nums[i] in the array, and return the array in a sorted order.
Example 1:
Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]
Example 2:
Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]
Constraints:
1 <= nums.length <= 200-100 <= nums[i], a, b, c <= 100nums is sorted in ascending order.
Follow up: Could you solve it in O(n) time?
Solutions#
Solution 1#
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
| class Solution:
def sortTransformedArray(
self, nums: List[int], a: int, b: int, c: int
) -> List[int]:
def f(x):
return a * x * x + b * x + c
n = len(nums)
i, j, k = 0, n - 1, 0 if a < 0 else n - 1
res = [0] * n
while i <= j:
v1, v2 = f(nums[i]), f(nums[j])
if a < 0:
if v1 <= v2:
res[k] = v1
i += 1
else:
res[k] = v2
j -= 1
k += 1
else:
if v1 >= v2:
res[k] = v1
i += 1
else:
res[k] = v2
j -= 1
k -= 1
return res
|
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
| class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
int n = nums.length;
int i = 0, j = n - 1, k = a < 0 ? 0 : n - 1;
int[] res = new int[n];
while (i <= j) {
int v1 = f(a, b, c, nums[i]), v2 = f(a, b, c, nums[j]);
if (a < 0) {
if (v1 <= v2) {
res[k] = v1;
++i;
} else {
res[k] = v2;
--j;
}
++k;
} else {
if (v1 >= v2) {
res[k] = v1;
++i;
} else {
res[k] = v2;
--j;
}
--k;
}
}
return res;
}
private int f(int a, int b, int c, int x) {
return a * x * x + b * x + c;
}
}
|
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
| class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
int n = nums.size();
int i = 0, j = n - 1, k = a < 0 ? 0 : n - 1;
vector<int> res(n);
while (i <= j) {
int v1 = f(a, b, c, nums[i]), v2 = f(a, b, c, nums[j]);
if (a < 0) {
if (v1 <= v2) {
res[k] = v1;
++i;
} else {
res[k] = v2;
--j;
}
++k;
} else {
if (v1 >= v2) {
res[k] = v1;
++i;
} else {
res[k] = v2;
--j;
}
--k;
}
}
return res;
}
int f(int a, int b, int c, int x) {
return a * x * x + b * x + c;
}
};
|
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
| func sortTransformedArray(nums []int, a int, b int, c int) []int {
n := len(nums)
i, j, k := 0, n-1, 0
if a >= 0 {
k = n - 1
}
res := make([]int, n)
for i <= j {
v1, v2 := f(a, b, c, nums[i]), f(a, b, c, nums[j])
if a < 0 {
if v1 <= v2 {
res[k] = v1
i++
} else {
res[k] = v2
j--
}
k++
} else {
if v1 >= v2 {
res[k] = v1
i++
} else {
res[k] = v2
j--
}
k--
}
}
return res
}
func f(a, b, c, x int) int {
return a*x*x + b*x + c
}
|
