题目
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.
解法
算法复杂度 O(n)，空间复杂度 O(n)。空间复杂度是由于需要存储返回的结果。
思路
直观解法，我们将数组进行重新排序，然后直接挨个计算平方，塞回到返回里面就可以了。这种解法并没有
利用数组原来就有序的特点，时间复杂度是 O(nlogn)。其实本质上数组分为三个部分：
- 小于 0
- 等于 0
- 大于 0
我们其实需要做一个正负两部分的 merge，因为都是各自有序。负数从 0 往左，正数从 0 往右，按照绝对值 进行 merge 就可以了。(这里不一定有0， 从最后一个负数，第一个正数往两端走即可)
下面代码还可以优化，例如减少 abs 的调用；代码逻辑可以简单点（判断全是正数或者全是负数合为一个）
代码
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;
}
};
本文完