Sort Transformed Array - Sắp xếp mảng sau biến đổi bậc hai

Cho mảng đã sắp xếp nums và các hệ số a, b, c. Áp dụng hàm bậc hai f(x) = ax² + bx + c cho mỗi phần tử. Trả về mảng kết quả đã sắp xếp.

Ví dụ: nums = [-4,-2,2,4], a=1, b=3, c=5 → [3,9,15,33].

Giải thuật (Hai con trỏ)

Hàm bậc hai có đồ thị parabol. Nếu a >= 0 (lồi lên), giá trị lớn nhất ở hai đầu → điền kết quả từ cuối về đầu. Nếu a < 0 (lồi xuống), giá trị nhỏ nhất ở hai đầu → điền từ đầu về cuối. So sánh f(nums[start]) và f(nums[end]) để quyết định lấy đầu nào.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    int f(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }

    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int n = nums.size();
        int start = 0, end = n - 1;
        vector<int> ret(n);

        if (a >= 0) {
            for (int i = n - 1; i >= 0; i--) {
                int x = f(nums[start], a, b, c);
                int y = f(nums[end], a, b, c);
                if (x > y) {
                    ret[i] = x;
                    start++;
                } else {
                    ret[i] = y;
                    end--;
                }
            }
        } else {
            for (int i = 0; i < n; i++) {
                int x = f(nums[start], a, b, c);
                int y = f(nums[end], a, b, c);
                if (x < y) {
                    ret[i] = x;
                    start++;
                } else {
                    ret[i] = y;
                    end--;
                }
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {-4,-2,2,4};
    print_vector(ob.sortTransformedArray(v, 1, 3, 5));
    return 0;
}

Đầu vào

{-4,-2,2,4}, 1, 3, 5

Đầu ra

[3, 9, 15, 33, ]