Leetcode 977. Square of ordered array

Power button | 977. The square of an ordered array

Title screenshot

Method 1 ： Direct sort

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(num * num for num in nums)

All codes for testing

from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(num * num for num in nums)
    
class main:
    a = Solution()
    nums = [-5,-3,-2,-1]
    b = a.sortedSquares(nums)

    print(b)

if __name__ == '__main__':
    main()

sorted() function

Python sorted() function | Novice tutorial

Method 2 ： Double pointer

The title is Non decreasing sort , The order may change after the square just depends on whether the original array element is zero .

Use the following code to record the subscript of the negative number .

        for i in range(0, n):
            if nums[i]<0:
                flag = i
            else:
                break

  You can also use enumerate() function

Python enumerate() function | Novice tutorial

for i, num in enumerate(nums):
            if num < 0:
                flag = i
            else:
                break

expand ： Realize it by yourself enumerate() function

def my_enumerate(obj):
    for i in range(len(obj)):
        yield i,obj[i]

  Set the left and right pointers respectively left=flag,right=flag+1, The left pointer points to the first negative number , Move to the left . The right pointer points to the first nonnegative number , To the right .

Set the loop , As long as the left and right pointers do not reach the leftmost and rightmost , It's been circulating .

Give priority to two extreme situations , namely , Make the pointer on the far left , But the right pointer did not reach the far right ; And the right pointer is on the far right , But the left pointer did not reach the leftmost .

1. When the left pointer is at the leftmost , Always add the element pointed to by the right pointer , And constantly move the right pointer to the right .

2. Reverse the same 2 The reason is .

3. When the left pointer points to an element less than or equal to the right pointer points to an element ： Add the element on the left , And move the left pointer to the left .

4. Reverse the same 3 The reason is .

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        flag = 0
        for i in range(0, n):
            if nums[i]<0:
                flag = i
            else:
                break
        left, right = flag, flag+1
        ans = []
        while left >= 0 or right < n:
            if left < 0:
                ans.append(nums[right] * nums[right])
                right += 1
            elif right == n:
                ans.append(nums[left] * nums[left])
                left -= 1
            elif (nums[left]*nums[left]) <= (nums[right] * nums[right]):
                ans.append(nums[left] * nums[left])
                left -= 1
            else:
                ans.append(nums[right] * nums[right])
                right += 1
        return ans

Method 3 ： Double pointer

Put the two pointers on the left and right sides at the beginning , Compare the size of the square of the element pointed to by the pointer and discharge it into the array , Let them move towards the middle .

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left, right, pos= 0, n-1, n-1
        ans = [0]* n
        while left <= right :
            if nums[left] * nums[left] > nums[right] * nums[right]:
                ans[pos] = (nums[left] * nums[left])
                left += 1
            else:
                ans[pos] = (nums[right] * nums[right])
                right -=1
            pos -= 1
        return ans