977. Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.



Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]


Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.


Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

这题最直接就是先按绝对值进行排序，然后做平方。

class SquaresofASortedArray : public Solution {
public:
    void Execute() {

    }

    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res;
        std::sort(nums.begin(), nums.end(), [](int l, int r) -> bool {
            return abs(l) < abs(r);
        });
        for (auto &v : nums) {
            v *= v;
        }
        return nums;
    }
};

Follow up提出了有O(N)的解法，怎么解呢。

之前审题不仔细，发现给出的是一个已经排序过后的数组，那么就简单了，首尾指针指一下即可，把大的数字放入结果数组的末尾就行了。

vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res;
        res.resize(nums.size(), 0);
        int head = 0, tail = nums.size() - 1;
        int ipos = nums.size() - 1;

        while (head <= tail) {
            if (abs(nums[head]) > abs(nums[tail])) {
                res[ipos--] = (nums[head] * nums[head]);
                ++head;
            } else {
                res[ipos--] = (nums[tail] * nums[tail]);
                --tail;
            }
        }
        return res;
    }