360. Sort Transformed Array - cocoder39/coco39_LC GitHub Wiki

360. Sort Transformed Array

use two pointers because the property of f(x). if a > 0, then the greatest value comes from two ends of nums[] if a < 0, then the smallest value comes from two ends of nums[] if a == 0, f() is a liner function, local max/min comes from two ends of nums[]

vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        vector<int> res(nums.size());
        int i = 0, j = nums.size() - 1;
        int start = 0, end = nums.size() - 1;
        while (i <= j) {
            if (a > 0) { //the greatest value comes from two ends
                res[end--] = f(nums[i], a, b, c) > f(nums[j], a, b, c) ? f(nums[i++], a, b, c) : f(nums[j--], a, b, c);
            }
            else {
                res[start++] = f(nums[i], a, b, c) < f(nums[j], a, b, c) ? f(nums[i++], a, b, c) : f(nums[j--], a, b, c);
            }
        }
        return res;
    }
private:
    int f(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
⚠️ **GitHub.com Fallback** ⚠️