164일 (977. Squares of a Sorted Array) Two pointers

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?

 

 

- 접근방법

 

nums[i] *= nums 한다.

Arrays.sort(nums)를 한다.

nums를 리턴한다.

하지만 자바에 내장되어 있는 배열 정렬알고리즘은 O(n log n)의 시간복잡도를 갖는다.

하지만 nums의 특성 때문에 투 포인터를 이용하면 O(n)의 시간복잡도와 O(n)의 공간복잡도로 위 문제를 풀 수 있다.

 

1. O(n)의 새로운 공간 answer와 배열의 양 끝을 가르키는 ptr1, ptr2를 초기화한다. 

 

2. 절댓값이 가장 큰 수를 answer배열의 마지막부터 위치시킨다.

→  nums의 중앙값에서 왼쪽으로 갈수록 음수는 커지고, nums의 중앙값에서 오른쪽으로 갈수록 양수는 커진다.

따라서 투 포인터를 이용하여 nums배열에서 음수든 양수든 상관없이 절댓값이 가장 큰 수의 제곱이 answer배열의 마지막에 올 것이다. 

(투 포인터를 이용하여 O(n)의 시간복잡도로 정렬 완료)

 

 

- 코드

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length; // 1
        int[] answer = new int[n];
        int ptr1 = 0;
        int ptr2 = n-1;

        for(int i = 0; i < n; i++) { // 2
            if(Math.abs(nums[ptr1]) > Math.abs(nums[ptr2])) {
                answer[i] = (int) Math.pow(nums[ptr1], 2);
                ptr1++;
            }
            else {
                answer[i] = (int) Math.pow(nums[ptr2], 2);
                ptr2--;
            }
        }

        return answer;
    }
}

 

배열의 내부 정렬에는 O(n log n)의 시간이 필요하지만

새로운 공간 O(n)을 선언하고 O(n)의 시간복잡도로 정렬을 완료할 수 있었다.

 

하지만 이는 nums의 특징 때문에 가능하였다.

배열의 중앙값을 기준으로 좌 우로 갈수록 절댓값이 순차적으로 커지는 특징을 가지고 있었기 때문에 투포인터를 이용하여 정렬할 수 있었다.

(어떻게 보면 nums는 정렬된 2개의 배열로 이루어져있는 것과 같기 때문에)

 

 

 

 

 

https://leetcode.com/problems/squares-of-a-sorted-array

Squares of a Sorted Array - LeetCode