Fork me on GitHub

Sort Transformed Array

Posted on

Description

Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic 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:

1
2
Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

Example 2:

1
2
Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]

Solution

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
class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        vector<int> ret(nums.size());
        
        if (a == 0) {
            int index = b >= 0 ? 0 : nums.size() - 1;
            int bias = b >= 0 ? 1 : -1;
            for (auto& item : nums){
                ret[index] = cal(a, b, c, item);
                index += bias;
            }
            return ret;
        }
        int index = a > 0 ? nums.size() - 1 : 0;
        int bias = a > 0 ? -1 : 1;
        auto left = 0;
        auto right = nums.size() - 1;
        while(left <= right) {
            int lValue = cal(a, b, c, nums[left]);
            int rValue = cal(a, b, c, nums[right]);
            ret[index] = a < 0 ? min(lValue, rValue) : max(lValue, rValue);
            int none = (ret[index] == lValue) ? ++left : --right;
            index += bias;
        } 
        
        return ret;
    }
    
    int cal(int a, int b, int c, int x) {
        return a*x*x + b*x + c;
    }
};