難度: Easy
類型: Array,Two Pointers,Sorting
CPP程式下載: 977.cpp
Topic:
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100] Explanation: After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100].
Example 2:
Input: nums = [-7,-3,2,3,11] Output: [4,9,9,49,121]
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104numsis sorted in non-decreasing order.
Consideration:
Integer has negative and positive integer. The larger element square should be located in the most left or most right position in a sorted vector. So, two pointers to check the most left and right elements. It could achieve O(n) complexity level.
Code:
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int num = nums.size();
//cout << "num = " << num << "\n";
//if (num==0) return nullptr;
vector<int> output_nums(nums);
int i=0, j=num-1, k=num-1, x2, y2;
for (;k>=0;k--)
{
if (j>=i)
{
x2 = nums.at(i) * nums.at(i);
y2 = nums.at(j) * nums.at(j);
if (y2 >= x2)
{
output_nums.at(k) = y2;
j--;
}
else
{
output_nums.at(k) = x2;
i++;
}
}
}
return output_nums;
}
