360. 有序转化数组

English Version

题目描述

给你一个已经 排好序 的整数数组 nums 和整数 a、b、c。对于数组中的每一个数 x，计算函数值 f(x) = ax² + bx + c，请将函数值产生的数组返回。

要注意，返回的这个数组必须按照 升序排列，并且我们所期望的解法时间复杂度为 O(n)。

示例 1：

输入: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
输出: [3,9,15,33]

示例 2：

输入: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
输出: [-23,-5,1,7]

解法

双指针。

利用抛物线的性质，i，j 分别指向排序数组首尾，从两端向中间夹逼。

• 若 a > 0，抛物线向上，两端具有最大值，比较两端点的较大值，添加到结果数组。
• 若 a < 0，抛物线向下，两端具有最小值，比较两端点的较小值，添加到结果数组。
• 若 a == 0，合并到以上的任意一种情况均可。

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
}

...