Array
Math
Two Pointers
Sorting
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 <= 100
nums
is sorted in ascending order.
Follow up: Could you solve it in O(n)
time?
Solutions
Solution 1
Python3 Java C++ Go
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
}
GitHub