C++ O(n) clean solution, compare distance instead of the value of polynomial equation


  • 0
    B
    class Solution {
    public:
        vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
    
            // solution 2, similar idea as solution 1, but compare from the index as size()-1 and 0,
            // instead of looking for lower_bound()
            int n = nums.size();
            vector<int> res(n, 0);
            int index = (a>0 || a==0 && b>0) ? n-1 : 0;
            double mid = 0;
            if(a!=0) mid= -1.0*double(b)/(2.0*a);
            int start = 0, end = n-1;
            while(start<=end){
                if(a!=0){
                    int x;
                    if(double(nums[end])-mid > mid-nums[start]) x = nums[end--];
                    else x = nums[start++];
                    if(a>0) res[index--] = a*x*x + b*x +c;  // index starts from n-1
                    else if(a<0) res[index++] = a*x*x + b*x +c;  // index starts from 0
                }
                else if(a==0){
                    int x = nums[end--];
                    if(b>0) res[index--] = a*x*x + b*x + c;
                    else    res[index++] = a*x*x + b*x + c;
                }
            }
            
            return res;
        }
    };

Log in to reply
 

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