Leetcode # 977. Squares of a Sorted Array

https://leetcode.com/problems/squares-of-a-sorted-array/

First Solution

注意 nums 僅有負數的場合！

Time Complexity: O(len(nums))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def sortedSquares(self, nums: List[int]) -> List[int]:
    i = 0
    while i < len(nums):
      if nums[i] >= 0:
        break
      i += 1
    
    ans = []
    i -= 1
    for j in range(i + 1, len(nums)):
      while i >= 0 and -1 * nums[i] < nums[j]:
        ans.append(nums[i] ** 2)
        i -= 1
      ans.append(nums[j] ** 2)
    
    // For situation which all(n < 0 for n in nums)  
    for j in range(i, -1, -1):
      ans.append(nums[j] ** 2)
      
    return ans

Refined Solution: Two Pointers

上一個 solution 是先找到正負的分界點
(all(n < 0 for n in nums[:i]) and all(n >= 0 for n in nums[i + 1:]))
再向頭尾去，abs(nums[i]) 和 abs(nums[j]) 則越來越大

反過來我們從頭尾開始
往絕對值越來越小的方向集中
能使得 code 更簡潔
（參考 template）

Time Complexity: O(len(nums))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def sortedSquares(self, nums: List[int]) -> List[int]:
    ans = collections.deque()
    left, right = 0, len(nums) - 1
    while left < right:
        
      if abs(nums[left]) > abs(nums[right]):
        ans.appendleft(nums[left] ** 2)
        left += 1
      else:
        ans.appendleft(nums[right] ** 2)
        right -= 1

    ans.appendleft(nums[left] ** 2)
    return ans

別忘記脫離 while left < right: 後
還有最後一個元素 nums[left] ≡ nums[right] 要處理！

Last Updated on 2023/08/16 by A1go