(C++) LeetCode 977 : 정렬된 배열의 제곱

문제

정렬된 배열의 제곱 – LeetCode

이 실제 인터뷰 질문을 해결할 수 있습니까? 정렬된 배열의 제곱 – 비내림차순으로 정렬된 정수 배열 nums가 주어지면 비내림차순으로 정렬된 각 숫자의 제곱 배열을 반환합니다. 예 1: 입력: 숫자 = (-4,-1,0,3,10) 꺼짐

'추천 관련글,

leetcode.com

암호

class Solution
{
    public:
        vector<int> sortedSquares(vector<int> &nums)
        {
            for (int &i: nums)
            {
                i *= i;
            }

            vector<int> res(nums.size());
            int idx = nums.size() - 1;
            int lo = 0;
            int hi = nums.size() - 1;

            while (idx != -1)
            {
                res(idx--) = (nums(lo) < nums(hi)) ? nums(hi--) : nums(lo++);
            }
            return res;
        }
};

설명

문제는 벡터의 모든 숫자를 제곱하고 오름차순으로 정렬하는 것입니다.
문제 설명을 그대로 따르면 O(n log n)으로 풀 수 있지만, 2 포인터 알고리즘을 사용하면 O(n)으로 풀 수 있다.

먼저 벡터의 모든 숫자를 제곱합니다.
그런 다음 첫 번째 숫자 lo와 마지막 숫자 hi를 비교합니다.
lo 또는 hi 값이 최대값입니다. 둘 중 더 큰 것은 결과 벡터 res의 끝에 저장됩니다.
마우스 포인터를 해당 lo 또는 hi의 가운데로 한 칸 이동합니다.
res는 제곱의 최대값부터 끝까지 채워지므로 오름차순 정렬과 동일합니다.