[数据结构与算法]#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.

Examples

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 <= $10^4$
-$10^4$ <= nums[i] <= $10^4$
nums is sorted in non-decreasing order.

思路

最简单的应该就是先square再sort，但这样时间复杂度会上去，但他的input是非递减的，所以可以用 2 pointer 进行，从两头向中间走

代码

class Solution {
    public int[] sortedSquares(int[] nums) {
        int pointer1 = 0, pointer2 = nums.length - 1;
        int[] answer = new int[nums.length];
        int pointer = nums.length - 1;
        
        boolean flag = false;
        while (pointer != -1){
            if (nums[pointer1] > 0){
                flag = true;
                break;
            }
            
            if (nums[pointer2] < 0)
                break;
            
            if (-nums[pointer1] > nums[pointer2]){
                answer[pointer] = nums[pointer1] * nums[pointer1];
                pointer1 ++;
            }
            else{
                answer[pointer] = nums[pointer2] * nums[pointer2];
                pointer2 --;
            }
            pointer --;
        }
        
        if (pointer != -1){
            if (flag){
                while (pointer != -1){
                    answer[pointer] = nums[pointer2] * nums[pointer2];
                    pointer2 --;
                    pointer --;
                }
            }
            else{
                while (pointer != -1){
                    answer[pointer] = nums[pointer1] * nums[pointer1];
                    pointer1 ++;
                    pointer --;
                }
            }
        }
        
        return answer;
    }
}