977. Squares of Sorted Array

發表於 分類於 ， 閱讀次數： Disqus： 文章字數： 189

種類 : list
難度 : easy
題目 : 977. Squares of Sorted Array

思維邏輯

  1. 設left在首，right在末
  2. 兩側向內歷遍，並將結果輸出至新list
  3. 反轉list

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def sortedSquares(nums: list) -> list:
        new_nums = []
        left = 0
        right = int(len(nums)) - 1
        while left <= right:
            if nums[left]**2 > nums[right]**2:
                new_nums.append(nums[left]**2)
                left += 1
            else:
                new_nums.append(nums[right]**2)
                right -= 1
        
        return new_nums[::-1]

時間複雜度: O(n)
空間複雜度: O(1)

難點

  1. 定義point邊界
  2. 輸出是由大至小(最後反轉)

最佳解法

此為較佳解法

其他解法
1
2
3
4
5
6
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[i] = nums[i] * nums[i]
        nums.sort()
        return nums

平方後，使用python函數sort()
時間複雜度: O(n log(n))
空間複雜度: O(1)