[Leetcode] 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?

 

[ 내 코드 ]

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> result;
        int size = nums.size();
        result.reserve(size);


        int plusIdx = 0;
        while (plusIdx < size && nums[plusIdx] < 0) plusIdx++;

        int minusIdx = plusIdx - 1;

        while (minusIdx >= 0 && plusIdx >= 0 && plusIdx < size)
        {
            if (Abs(nums[minusIdx]) > Abs(nums[plusIdx]))
            {
                result.push_back(nums[plusIdx] * nums[plusIdx]);
                plusIdx++;
            }
            else
            {
                result.push_back(nums[minusIdx] * nums[minusIdx]);
                minusIdx--;
            }
        }

        while (minusIdx >= 0)
        {
            result.push_back(nums[minusIdx] * nums[minusIdx]);
            minusIdx--;
        }

        while (plusIdx < size && plusIdx >= 0)
        {
            result.push_back(nums[plusIdx] * nums[plusIdx]);
            plusIdx++;
        }

        return result;
    }

    int Abs(int num)
    {
        return num < 0 ? -num : num;
    }
};

 

[ 상위 점수 코드 ]

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        size_t size = nums.size();
        vector<int> result(size, 0);

        int left = 0;
        int right = size - 1;

        int cnt = 0;

        for (int i = size - 1; i >= 0; i--)
        {
            if (std::abs(nums[left]) > std::abs(nums[right]))
            {
                result[i] = (nums[left] * nums[left]);
                left++;
            }
            else
            {
                result[i] = (nums[right] * nums[right]);
                right--;
            }
        }

        return result;
    }
};

 

- 음수 시작지점, 양수 시작지점을 구한다음 절대값이 더 큰 녀석을 하나씩 result vector에 때려 넣는 방법으로 정답은 맞추었으나 생각보다는 코드가 복잡했다.

- 수행속도 상위 코드를 보니 훨씬 간단했는데 맨왼쪽, 맨오른쪽부터 서로 비교해 절대값이 큰값으로 뒤쪽부터 채워넣는 방식으로 하니 훨씬 코드가 간단했다.

 

- 뒤에서부터 때려넣는 방식을 생각해냈다면 좋았을 것 같다.