[LeetCode] 977. Squares of a Sorted Array - 문제풀이

Description

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
• -10^4 <= nums[i] <= 10^4
• 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?

Solution 1. Sort - 정렬

public int[] sortedSquares(int[] nums) {
    // 1. using sort 
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        nums[i] = nums[i]*nums[i];
    }
    Arrays.sort(nums);
    return nums;
}

배열 순서대로 제곱한 뒤 Arrays.sort() 정렬하여 반환합니다.

• 시간 복잡도 - O(N logN)
• 공간 복잡도 - O(1)

Solution 2. Two pointers

public int[] sortedSquares2(int[] nums) {
    // 2. Two pointers
    int len = nums.length;
    int start = 0; // 기존 배열 포인터1
    int end = len-1; // 기존 배열 포인터2
    int i = len-1; // 새로운 배열의 포인터
    int[] result = new int[len];
    while(start <= end){ //제곱은 절대값이니 양끝에 포인터를 두고 절대값이 큰 것 부터 새로운 배열 끝에서부터 채워넣음
        if(Math.abs(nums[start]) <=  Math.abs(nums[end])){
            result[i] = nums[end]*nums[end];
            end--;
        }else{   // start가 더 큰 경우 end
            result[i] = nums[start]*nums[start];
            start++;
        }
        i--;
    }
    return result;
}

두개의 포인터를 이용하는 방법입니다. 정렬된 배열(nums)의 양끝의 절대값이 가장 큰 값이기 때문에 둘 중 큰값부터 오른쪽에 채워넣고 포인터를 이동시킵니다.

양쪽 포인터가 만나서 모든 요소를 새로운 배열에 채워넣으면 result를 반환해 주면 됩니다.

• 시간 복잡도 - O(N logN)
• 공간 복잡도 - O(N)

Reference

Squares of a Sorted Array - LeetCode