977. Squares of a Sorted Array

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] <= 104
• nums is sorted in non-decreasing order.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

 

# 풀이 

난 그냥 단순히 제곱근 구하기, 절대값 구하는 함수를 써서 풀었긴 했다. 근데 이건 Two Pointer 테마니까 .... 

> 내 풀이 (100ms ......)

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i=0;i<nums.size(); i++) {
            nums[i] = pow(nums[i], 2);
        }
        //for(int i : nums) cout << i << ' ';
        sort(nums.begin(), nums.end());
 
        return nums;
    }
};

 

> Two Pointer 풀이 (26 ms)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
vector<int> nums = {-4,-2,0,1,3};
 
vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();
    int l = 0;
    int r = n-1;
    
    vector<int> res(n);
    int pos = n-1;
    
    while(l <= r) {
        if(abs(nums[l]) < abs(nums[r])) {
            res[pos--] = pow(nums[r],2);
            r--;
        } else {
            res[pos--] = pow(nums[l],2);
            l++;
        }
    }
    return res;
}
 
 
int main()
{
    nums = sortedSquares(nums);
    for(int i : nums) cout << i << ' ';
    return 0;   
}