C++_Accpeted_6ms_64.58%


  • 0

    Actually it's a pure math problem, LOL

    class Solution {
    public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        if(nums.empty()) return {};
        int n = nums.size();
        vector<int> res;
        if(a == 0){
            res.resize(n);
            if(b == 0){
                for(int i = 0; i < n; ++i){res[i] = c;}
            }else if(b > 0){
                for(int i = 0; i < n; ++i){res[i] = b * nums[i] + c;}
            }else{
                for(int i = n - 1; i >= 0; --i){res[n - 1 - i] = b * nums[i] + c;}
            }
        }else{//a != 0
            double val = - (b * 1.0) / (2 * a * 1.0);
            int k = 0, i = 0, j = 0;
            while(nums[k] * 1.0 < val){++k;}
            if(a > 0){
                i = k - 1;
                j = k;
                while(i >= 0 && j <= n - 1){
                    int I = nums[i], J = nums[j];
                    if(abs(I - val) < abs(J - val)){res.push_back(a*I*I + b*I + c); --i;}
                    else{res.push_back(a*J*J + b*J + c); ++j;}
                }
                while( i >= 0 ){
                    int I = nums[i];
                    res.push_back(a*I*I + b*I + c);
                    --i;
                }
                while(j <= n - 1){
                    int J = nums[j];
                    res.push_back(a*J*J + b*J + c); ++j;
                }
            }else if(a < 0){//a < 0
                i = 0;
                j = n - 1;
                while(i < k && j >= k){
                    int I = nums[i], J = nums[j];
                    if(abs(I - val) > abs(J - val)){res.push_back(a*I*I + b*I + c); ++i;}
                    else{res.push_back(a*J*J + b*J + c); --j;}
                }
                while( i < k ){
                    int I = nums[i];
                    res.push_back(a*I*I + b*I + c);
                    ++i;
                }
                while(j >= k){
                    int J = nums[j];
                    res.push_back(a*J*J + b*J + c);
                    --j;
                }
            }
        }
        return res;
    }
    };
    

    0_1476752537291_628FB8C4-5C6D-4C63-BC77-5382F5049EEC.png


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.