[LeetCode] Squares of a Sorted Array

leetcode.com/explore/learn/card/fun-with-arrays/521/introduction/3240/

 

- 정수 숫자가 담긴 배열이 주어집니다. 그것은 오름차순으로 정렬되어있습니다. 그것의 제곱들을 오름차순으로 리턴하세요.

- 음수 시작인 경우 양수로 전환 하는 곳을 지점으로 오른쪽 i, 왼쪽 j 인덱스를 비교하면서 작은 수부터 배열에 담으면 됨. 같을 경우 아무거나 상관없음. i를 해도 됨. 처음과 끝 인덱스를 넘어가지 않도록 조심하면 됨.

- 양수 시작인 경우는 바로 배열에 담으면 됨. 

- O(N) 풀이법이 있음... 으음....

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> newArr;
        int l, r = 0;
        int pivot = 0;

        if (nums[0] < 0) {
            for (int i = 1; i < nums.size(); i++) {
                if (nums[i] >= 0) {
                    pivot = i;
                    break;
                }
                
            }
            newArr.push_back(nums[pivot] * nums[pivot]);
            l = pivot - 1; r = pivot + 1;
            while (l >= 0 && r < nums.size()) {
                if (nums[l] * nums[l] >= nums[r] * nums[r]) {
                    newArr.push_back(nums[r] * nums[r]);
                    r++;
                }
                else {
                    newArr.push_back(nums[l] * nums[l]);
                    l--;
                }
            }
            while (l >= 0) {
                newArr.push_back(nums[l] * nums[l]);
                l--;
            }
            while (r < nums.size()) {
                newArr.push_back(nums[r] * nums[r]);
                r++;
            }
        }
        else {
            r = 0;
            while (r < nums.size()) {
                newArr.push_back(nums[r] * nums[r]);
            }
        }
        return newArr;
    }
};

- discussion 을 본 풀이. 

- vector의 사이즈가 runtime에 결정될 수 있구나.

- abs, res(A.size()) API. 절대값구하는 함수, 처음 벡터 사이즈 정하는 함수

- 음수 시작 양수 시작이 아닌 일반화하여 풀이 가능

- 아 애초에 작은 수부터 쌓는 것이 아니라, 가장 큰 수부터 쌓는 것이므로.

- 처음 생각한 코드의 최악의 경우에는 2N인데, 이것은 정말 딱 N이구나.

- 처음 생각한 코드는 O(N)이지만 실제 Wort로는 2N임.

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        vector<int> res(A.size());
        int l = 0, r = A.size()-1;
        for(int k=A.size()-1; k>=0; k--){
            if(abs(A[r]) > abs(A[l])) res[k] = A[r] * A[r--];
            else res[k] = A[l] * A[l++];
        }
        return res;
    }
};