题目描述:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:
最容易想到的方法就是先平方再排序,这样时间复杂度O(nlogn)
但是这题有A的非递减特性可以利用,非负数的平方还是一个非递减顺序,负数的平方是一个非递增序列,将其逆序就是非递减序列了。于是可以先找到非负数和负数的分界线,然后使用双指针依次比较非负数和负数平方后的数值,填入较小的数值,指针后移。
然后注意双指针的边界条件即可。
时间复杂度是O(n),我使用一个临时数组存储了序列平方后的数值,空间复杂度O(n)。因为个人觉得如果每次都将数平方比较的话,乘法运算耗时较长,所以使用了临时数组。
代码:
class Solution {
private:
vector<int> ans;
public:
/**
给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。
**/
vector<int> sortedSquares(vector<int>& A) {
// 找到数组中非负数和负数的分界位置
int i = 0; // i指向非负数的第一个位置
while (i <= A.size()-1) {
if (A[i] < 0) {
++i;
}else break;
}
int size = (int)A.size();
if (i == A.size()) {// 没有非负数,即全是负数,则其平方逆序即可
ans.resize(A.size());
for (int i = 0; i < A.size(); ++i) {
ans[size-1-i] = A[i]*A[i];
}
}else{
// 存在非负数,需要对平方后的逆序和正序序列归并排序
vector<int> tmp;
tmp.resize(size);
for (int k = 0; k < A.size(); ++k) {
tmp[k] = A[k]*A[k];
}
int left = i-1, right = i;
while (left >= 0 && right < size) {
if (tmp[left] <= tmp[right]) {
ans.push_back(tmp[left]);
--left;
}else{
ans.push_back(tmp[right]);
++right;
}
}
while (left >= 0) {
ans.push_back(tmp[left]);
--left;
}
while (right < size) {
ans.push_back(tmp[right]);
++right;
}
}
return ans;
}
};
Comments | 0 条评论