7-line and 9-line concise solutions with explanation


  • 1
    C
    1. a > 0: y = a*x*x+b*x+c => y value goes down and goes up

    1. a < 0: y value goes up and goes down

    A list is used for insertion since it may be inserted before or after. For every entry, the right position is computed. This may sound like O(n^2) or O(nlogn). Assuming case 1 without loss of generality, the iterator (location/index finder) initially travels down and eventually travels up due to the property of the function. It consumes at most O(2n) for inner and outer loop. For the final step, list data is copied into output.

    class Solution {
    public:
        vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
            list<int> l;
            list<int>::iterator it = l.begin();
            for (auto& x: nums) {
                int y = a*x*x + b*x + c;
                while (it != l.begin() && *it > y) it--;
                while (it != l.end() && *it < y) it++;
                it = l.insert(it, y);
            }
            return vector<int>(l.begin(), l.end());
        }
    };
    

    The first solution is what I came up when doing the question myself. After reading other posts, I just rewrite another way of doing it. The detail explanation can be found in this link.

    class Solution {
    public:
        vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
            vector<int> res(nums.size()), y;
            for (auto &x: nums) y.emplace_back(a*x*x+b*x+c);
    
            int i = 0, j = nums.size()-1, k = a<0? 0: nums.size()-1;
            for(; i <= j; k += a<0? 1: -1) {
                if (y[i] < y[j] == a < 0) res[k] = y[i++];
                else                      res[k] = y[j--];
            }
            return res;
        }
    };
    

  • 0
    This post is deleted!

  • 0

    Nice solutions, I particularly like the first one because I hadn't seen that before.

    Just one not so nice thing: Both the problem and your own text call the elements "x" and the number of elements "n", but your code then goes against all that and calls the elements "n".


  • 0
    C

    Thanks for the suggestion! Fix it now.


Log in to reply
 

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