977 有序数组的平方
暴力做法
每个数平方之后再使用sort()排序
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for(int i = 0; i < nums.size(); i++){
nums[i] *= nums[i];
}
sort(nums.begin(),nums.end());
return nums;
}
};
时间复杂度: \(O(n + nlogn)\)
空间复杂度: \(O(n)\)
双指针法
观察数组,我们可以发现,位于数组两端的数的绝对值比中间大,因此它们的平方值也比中间大
因此我们可以从两端向中间遍历比较,将较大值放入新数组中
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
// 新数组末尾元素的位置
int k = n - 1;
// 新开一个数组
vector<int> res(n, 0);
// 左闭右闭区间[0,k]
int left = 0, right = k;
// 左闭右闭区间[left,right]
while(left <= right){
int leftSquare = nums[left] * nums[left];
int rightSquare = nums[right] * nums[right];
if(leftSquare > rightSquare){
// 题目要求数组非递减顺序,因此较大值放在数组末尾
res[k--] = leftSquare;
left++;
}
else{
res[k--] = rightSquare;
right--;
}
}
return res;
}
};
时间复杂度: \(O(n + nlogn)\)
空间复杂度: \(O(n)\)