# Squares of a Sorted Array

Posted by chunyang on April 5, 2019

### 题目

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

Example 1:

Input: [-4,-1,0,3,10]

Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]

Output: [4,9,9,49,121]

Note:

• 1 <= A.length <= 10000
• -10000 <= A[i] <= 10000
• A is sorted in non-decreasing order.

### 解法

• 小于 0
• 等于 0
• 大于 0

#### 代码

class Solution {
private:
/* used to sort according to abs of value in std::sort of stl */
struct Comp {
bool operator()(const int& lhs, const int& rhs) {
int a = abs(lhs);
int b = abs(rhs);
if (a < b) {
return true;
} else {
return false;
}
}
};
public:
vector<int> sortedSquares(vector<int>& A) {
if (A.empty()) {
return vector<int>();
}
vector<int> result;
int length = A.size();
if (A[0] < 0) {
int first_neg = 0;
while (first_neg < length && A[first_neg] < 0) ++first_neg;
if (first_neg == length) {
while (length > 0) {
result.push_back(A[length-1] * A[length - 1]);
--length;
}
} else {
int first_pos = first_neg;
--first_neg;
while (first_neg >= 0 || first_pos < length) {
if (first_neg >= 0 && first_pos < length) {
auto a = A[first_pos];
auto b = abs(A[first_neg]);
result.push_back(a > b ? b * b: a * a);
a > b ? --first_neg : ++first_pos;
} else if (first_neg >= 0) {
auto b = abs(A[first_neg]);
result.push_back(b * b);
--first_neg;
} else if (first_pos < length) {
auto a = A[first_pos];
result.push_back(a*a);
++first_pos;
}
}
}
} else {
int i = 0;
while (i < length) {
result.push_back(A[i] * A[i]);
++i;
}
}
/* copy(A.begin(), A.end(), ostream_iterator<int>(cout, ", ")); */
return result;
}
};