Description

Squares of a Sorted Array - LeetCode

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?

Solution

• 문제 Follow up에 trivial하다는 솔루션으로 이미 풀어놓은 게 있었다.

public int[] sortedSquares(int[] nums) {
        int[] answer = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            answer[i] = (int) Math.pow(nums[i], 2);
        }
        Arrays.sort(answer);
        return answer;
}

• 오늘 컨셉은 투포인터인 것 같아 그렇게 풀어봤다
  • 배열에 음수와 양수가 같이 있는 경우, square 한 배열을 정렬하면 원 배열에 중간 인덱스값이 앞으로 오게 된다. 그러니까 원 배열의 양 끝에 있는 값이 square한 배열에서는 끝으로 갈 확률이 높다.
  • 포인터 둘을 선언하고 하나는 배열의 제일 앞에, 다른 하나는 배열의 제일 뒤에 오게 한 후 새 배열의 뒤에서부터 값을 넣어준다.

 public int[] sortedSquares2(int[] nums) {
        int p1 = 0, length = nums.length, p2 = length - 1;
        int[] answer = new int[nums.length];
        for (int i = length - 1; i >= 0; i--) {
            if (Math.abs(nums[p1]) >= Math.abs(nums[p2])) {
                answer[i] = nums[p1] * nums[p1];
                p1++;
            } else {
                answer[i] = nums[p2] * nums[p2];
                p2--;
            }
        }
        return answer;
}