LeetCode 筆記 - 977. Squares of a Sorted Array

要求將包含負數的已排序數列進行平方後再次排序。本文探討如何利用雙指針從兩端向中間掃描的技巧，巧妙處理負數平方後的數值變化，達成在 O(N) 線性時間內完成平方與排序的優化解法。

發佈

2022.05.17

閱讀

約 1 分鐘

字數

185

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

給一個 Sorting 過的數列，請將每個數字平方之後，再做一次排序

解題思維

直接做可以過

要加速可以在做平方的時候把負數都挑起來，然後針對只剩下自然數的數列做 merge
這樣可以加速一些 Sorting 的過程

1
2
3

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(list(map(lambda x: x ** 2, nums)))