360. Sort Transformed Array

Posted on Edited on In

360. Sort Transformed Array

Description

Difficulty: Medium

Related Topics: Array, Math, Two Pointers, Sorting

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:

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]

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?

Hints/Notes

Solution

Language: 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
36
class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int i = 0, j = nums.size() - 1, idx = 0;
        if (a >= 0) {
            idx = nums.size() - 1;
        }
        vector<int> res(nums.size(), 0);
        while (i <= j) {
            int v1 = f(a, b, c, nums[i]);
            int v2 = f(a, b, c, nums[j]);
            if (a < 0) {
                if (v1 < v2) {
                    res[idx++] = v1;
                    i++;
                } else {
                    res[idx++] = v2;
                    j--;
                }
            } else {
                if (v1 < v2) {
                    res[idx--] = v2;
                    j--;
                } else {
                    res[idx--] = v1;
                    i++;
                }
            }
        }
        return res;
    }

    int f(int a, int b, int c, int x) {
        return a * x * x + b * x + c;
    }
};