数组-有序数组的平方
题目链接
1
2
3
4
5
6
7
8
9
| 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;
}
};
|
如果用c++的话，如上的方法是最简单的，但是呢时间复杂度不符合进阶要求。
采用双指针方法，因为数组是有序的，头和尾的平方才有可能是最大值，不可能在中间，所以可以设定一个左指针和右指针，再定义一个数组来存放平方值，数组和原数组大小一样，设定一个k指针指向数组最终位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
int k = nums.size() - 1;
vector<int> result(nums.size(), 0);
while(left <= right){
if(nums[left] * nums[left] < nums[right] * nums[right]){
result[k--] = nums[right] * nums[right];
right--;
}
else{
result[k--] = nums[left] * nums[left];
left++;
}
}
return result;
}
};
|