Square of a Sorted Array

Given an array of integers A sorted in non-decreasing order,retrun an array of the squares of each number,also in sorted non-decreasing order.

Example

Input:[-4,-1,0,3,10]
Output:[0,1,9,16,100]

---

Tips

two point

---

Solution

there are two solutions.

1.Sort

just get every element square then sort list.

2.Two Point

• from the last element to the first.
• use two point left and right
• judge the left and right values which is bigger
• the bigger one sets to the current last element
• move point from last one to second last

std::vector<int> sortedSquares(std::vector<int> &A)
{
    int l = 0;
    size_t r = A.size();
    size_t p = A.size() - 1;
    std::vector<int> res(A.size());
    while (r > l)
    {
        int a = A[l] * A[l];
        int b = A[r - 1] * A[r - 1];
        if (a > b)
        {
            res[p] = a;
            l++;
        }
        else
        {
            res[p] = b;
            r--;
        }
        p--;
    }
    return res;
}

---