leetcode – Squares of a Sorted Array

问题

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 <= 10⁴
• -10⁴ <= nums[i] <= 10⁴
• 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?

解答:

平方后排序

新申请一个数组存放平方数，之后进行排序即可

时间复杂度 O(nlogn) 依赖与排序算法，如堆排序，并归排序

空间复杂度 O(n) 平方数组

# time complexity O(nlogn)  space complexity O(n)
def sortedSquaredArray(array):
    # Write your code here.
    sortedSquares = []
    for value in array:
        squareValue = value * value
        sortedSquares.append(squareValue)
    sortedSquares.sort()
    return sortedSquares

双指针

由于原有数组的排序的，平方和最大情况，可能会发生在数组两端， 通过两个指针从数组两端开始，比较将平方和大的放到新数组中。

时间复杂度 O(n) 依赖与排序算法，如堆排序，并归排序

空间复杂度 O(n) 平方数组

def sortedSquaredArray(array):
    # Write your code here.
    sortedSquares = [0  for _ in array]
    smallIdx = 0 
    largeIdx = len(array) - 1
    
    for idx in reversed(range(len(array))):
        smallerValue = array[smallIdx]
        largerValue = array[largeIdx]
        
        if abs(largerValue) > abs(smallerValue):
            sortedSquares[idx]  = largerValue * largerValue
            largeIdx = largeIdx - 1
        else:
            sortedSquares[idx] = smallerValue * smallerValue
            smallIdx = smallIdx + 1
        
    return sortedSquares

参考及引用

Photo by Erik Karits from Pexels