README_EN.md

360. Sort Transformed Array

中文文档

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

Python3

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

Java

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;
    }
}

C++

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;
	}
};

Go

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
}

...