[leetcode] 977 square of ordered array

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 .

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]

Tips ：

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

Advanced ：

Please design with a time complexity of O(n) The algorithm solves this problem

# Direct sort 
class Solution(object):
    def sortedSquares(self, nums):
        return sorted(num*num for num in nums)
# Time complexity ：O(n \log n)O(nlogn)
# Spatial complexity ：O(\log n)O(logn)

# Double pointer 
# Because the array sequence is in ascending order , Square is a positive number , So start at both ends , Numbers with large absolute values enter the sequence squared first 
class Solution(object):
    def sortedSquares(self, nums):
        a = 0
        b = len(nums)-1
        result = []
        while a<=b:
            if abs(nums[a])>=abs(nums[b]):
                result.append(nums[a]*nums[a])
                a+=1
            else:
                result.append(nums[b]*nums[b])
                b-=1
        return result[::-1]