Array - 977. Square of ordered array

1 Title Description

Here's a button Non decreasing order Sorted array of integers nums, return The square of each number A new array of , According to the requirements Non decreasing order Sort .

2 Title Example

Example 1：

Input ：nums = [-4,-1,0,3,10]
Output ：[0,1,9,16,100]
explain ： After square , The array becomes [16,1,0,9,100]
After ordering , The array becomes [0,1,9,16,100]

Example 2：

Input ：nums = [-7,-3,2,3,11]
Output ：[4,9,9,49,121]

3 Topic tips

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums Pressed Non decreasing order Sort

4 Ideas

Arrays are actually ordered , It's just that the negative square may be the maximum .

Then the maximum square of the array is at both ends of the array , Either the far left or the far right , It can't be in the middle .

At this point, we can consider the double pointer method ,i Point to the starting position ,j Point to the end position .

Define a new array result, and A Array size , Give Way k Point to result Array end position .

5 My answer

class Solution {
    
    public int[] sortedSquares(int[] nums) {
    
        int right = nums.length - 1;
        int left = 0;
        int[] result = new int[nums.length];
        int index = result.length - 1;
        while (left <= right) {
    
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
    
                //  The relative position of positive numbers is constant ,  What needs to be adjusted is the relative position after the square of the negative number 
                result[index--] = nums[left] * nums[left];
                ++left;
            } else {
    
                result[index--] = nums[right] * nums[right];
                --right;
            }
        }
        return result;
    }
}

class Solution {
    
    public int[] sortedSquares(int[] nums) {
    
        int l = 0;
        int r = nums.length - 1;
        int[] res = new int[nums.length];
        int j = nums.length - 1;
        while(l <= r){
    
            if(nums[l] * nums[l] > nums[r] * nums[r]){
    
                res[j--] = nums[l] * nums[l++];
            }else{
    
                res[j--] = nums[r] * nums[r--];
            }
        }
        return res;
    }
}