题目来源

• leetcode：360-VIP. 有序转化数组

题目描述

给你一个已经 排好序 的整数数组 nums 和整数 a、b、c。对于数组中的每一个数 x，计算函数值 f(x) = ax^2 + 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]

实现：

class Solution {
    
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c){
    
		
	}

题目解析

抛物线

思路

对于抛物线方程f(x) = ax^2 + bx + c 来说

• 如果a>0，则抛物线开口朝上，那么两端的值比中间的大
• 如果a<0，则抛物线开口朝下，则两端的值比中间的小
• 当a=0时，则为直线方法，是单调递增或递减的

又因为输入数组是有序的，所以我们可以根据a来分情况讨论：

• 当a > 0，说明两端的值比中间的大，此时我们从res从后往前填写（因为先得出的是大的值），用两个指针分别指向nums的开头和结尾，指向的两个数就是抛物线两端的数，将它们中较大的数先填入res末尾，然后指针向中间移，重复比较过程，直到把res都填满。
• 当a<0，说明两端的值比中间的小，那么我们从res的前面往后填，用两个指针分别指向nums数组的开头和结尾，指向的两个数就是抛物线两端的数，将它们之中较小的数先存入res的开头，然后指针向中间移，重复比较过程，直到把res都填满。
• 当a=0，函数是单调递增或者递减的，那么从前向后填写或者从后往前填写都可以，我们可以将这种情况和a > 0合并

实现

class Solution   {
    
    int cal(int x, int a, int b, int c){
    
        return a * x * x + b * x + c;
    }
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
    
        int N = nums.size(), i = 0, j = N - 1;
        std::vector<int> res(N);
        int idx = a >= 0 ? N - 1 : 0;
        while (i <= j){
    
            if(a >= 0){
    
                res[idx--] = cal(nums[i], a, b, c) >= cal(nums[j], a, b, c) ? cal(nums[i++], a, b, c) : cal(nums[j--], a, b, c);
            }else{
    
                res[idx++] = cal(nums[i], a, b, c) >= cal(nums[j], a, b, c) ? cal(nums[j--], a, b, c) : cal(nums[i++], a, b, c);
            }
        }
        return res;
    }
};

最小堆（O(nlgn)）

class Solution   {
    
    int cal(int x, int a, int b, int c){
    
        return a * x * x + b * x + c;
    }
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
    
        std::vector<int> res;
        std::priority_queue<int, vector<int>, std::greater<>> minPQ;
        for(int num : nums){
    
            minPQ.push(cal(num, a, b, c));
        }
        
        while (!minPQ.empty()){
    
            res.push_back(minPQ.top());
            minPQ.pop();
        }
        return res;
    }
};

类似题目

• 977.squares-of-a-sorted-array(有序数组的平方)