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

---

✍풀이

import java.util.Arrays;
class Solution {
    public int[] sortedSquares(int[] nums) {
        
        int[] result = new int[nums.length];
        for(int i = 0; i < nums.length; i++){
            nums[i] *= nums[i];
            result[i] = nums[i];
        }
        Arrays.sort(result);
        return result;
    }
}

---

class Solution {
    public int[] sortedSquares(int[] nums) {
        
        //결과를 저장할 배열 생성
        int[] res = new int[nums.length];
    
        // 두 포인터 초기화
        int left = 0;
        int right = nums.length - 1;
        
        //4,3,2,1,0 감소하며 인덱스에 저장
        //큰 값부터 차례대로 제곱된 값을 res배열에 저장
        for(int i = nums.length - 1; i >= 0; i--){
            //절대값을 비교하여 더 큰 값을 저장
            if(Math.abs(nums[left]) > Math.abs(nums[right])){
                res[i] = nums[left] * nums[left];
                left++;
            }else{
                res[i] = nums[right] * nums[right];
                right--;
            }
        }
        return res;
    }
}

작동 방식

• 포인터 초기화: left 포인터는 배열의 시작에서, right 포인터는 배열의 끝에서 시작합니다.

• 제곱 값 비교: for 루프를 사용하여 배열의 끝에서부터 시작하여 채워나갑니다. nums[left]와 nums[right]의 절대값을 비교하여 더 큰 값을 제곱하여 결과 배열 res에 저장합니다.

• 포인터 이동: 더 큰 값을 제곱하여 저장한 후, 해당 포인터를 이동합니다 (left++ 또는 right--).

• 반복: 배열의 모든 요소에 대해 위 과정을 반복하여 결과 배열을 채웁니다.

예제
입력 배열: [-4, -1, 0, 3, 10]

left = 0, right = 4
비교: |nums[0]| = 4, |nums[4]| = 10
nums[4]가 더 크므로 res[4] = 10 * 10 = 100, right--

left = 0, right = 3
비교: |nums[0]| = 4, |nums[3]| = 3
nums[0]가 더 크므로 res[3] = 4 * 4 = 16, left++

left = 1, right = 3
비교: |nums[1]| = 1, |nums[3]| = 3
nums[3]가 더 크므로 res[2] = 3 * 3 = 9, right--

left = 1, right = 2
비교: |nums[1]| = 1, |nums[2]| = 0
nums[1]가 더 크므로 res[1] = 1 * 1 = 1, left++

left = 2, right = 2
비교: |nums[2]| = 0, |nums[2]| = 0
nums[2]가 같으므로 res[0] = 0 * 0 = 0, right--

결과 배열: [0, 1, 9, 16, 100]