# 【LeetCode刷題】【演算法學習筆記】977. Squares of a Sorted Array
* 學習時間：2025/01/30 (Fir.)
* **題目連結（美服）：** [977. Squares of a Sorted Array](https://leetcode.com/problems/remove-element/description/)
* **題目連結（國服）：**[977.有序数组的平方](https://leetcode.cn/problems/squares-of-a-sorted-array/description/)
* **兄弟題：**
* **題目標籤：** ==陣列== ==雙指針== ==排序==

### A. 題目
---
>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]

### B. 題意（中文）
---
>给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

>示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

>示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]元素和 nums 的大小并不重要。

### C. 參考程式碼
---

:::spoiler Thinking（思路）
reference: [力扣官方题解](https://leetcode.cn/problems/squares-of-a-sorted-array/solutions/447736/you-xu-shu-zu-de-ping-fang-by-leetcode-solution/) [灵茶山艾府](https://leetcode.cn/problems/squares-of-a-sorted-array/solutions/2806253/xiang-xiang-shuang-zhi-zhen-cong-da-dao-blda6/)

#### 官方題解
* 寫法一：將陣列 nums 中的數平方後直接排序。
* 寫法二：雙指針
1. **為利用到陣列升序條件**
* 因為平方後可能會變成無序
* 所以使用 **neg** 區分元素正負值
* nums[0] 到 nums[neg] 為負數 ☞ 平方後會遞減
* nums[neg] 到 nums[n-1] 為正數 ☞ 平方後會遞增
2. **排序算法思路** ➡︎ ==雙指針==
* 指針指向 **neg** 和 非負數 **neg+1**
* 每次選擇較小數值加入陣列
* 剩餘部分直接加入結果

3. 範例：

* 寫法三：雙指針
* 一個指向位置 0，一個指向位置 n-1
* 比較兩指針數值，選擇較大的數值
* **逆序**放入陣列 ☞ 因為平方後會兩端大，中間小
* 例如：[-4, -2, 0, 3, 5]，平方：[16, 4, 0, 9, 25]
---
#### 靈神題解
* 寫法一：陣列分成負數 和 非負數
* 算法實現
💡 **雙指針從陣列兩端走向中間 ➡︎ 比較大小並合併**
* 初始化 ➡︎ 左指針：i = 0; 右指針：j = n-1; 新陣列：ans 下標為 p = n-1 (**逆序**放入陣列)
* 平方 ➡︎ nums[i]^2 nums[j]^2
* 大小比較 ➡︎ 大的填入 ans[p]，直到 p = -1
* 寫法二：
* 算法實現
💡 **比较 −nums[i] 和 nums[j] 的大小**
* 如果 nums 中的元素**均為負數** -nums[i] > 0 > num[j] 恆成立 ➡︎ [-7, -5, -3, -1]
* 如果 nums 中的元素**均為非負數** -nums[i] <= 0 <= num[j] ➡︎ [7, 5, 3, 1, 0]
* 如果 nums[i] < 0, nums[j] >= 0, 比較結果等價於 nums[i]^2, nums[j]^2 ➡︎ [-7, -5, -2, 0, 3, 1]

:::

:::spoiler Note（筆記）
**複雜度**
1. 平方後直接排序
* Time complexity: **O(nlogn)** ➡︎ n 為陣列長度
* Space complexity: **O(logn)** ➡︎ 儲存答案的陣列以外，我们需要 O(logn) 的 Stack Space 來排序。

2. 雙指針
* Time complexity：**O(n)** ➡︎ n 為陣列長度
* Space complexity: **O(1)** ➡︎ 直接在原陣列中修改（如就地排序），將空間複雜度優化到 O(1)，返回值不記錄。
* 補充：若使用了额外的空間儲存結果，Space complexity 將上升至 O(n)
:::

:::spoiler 官方題解一

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # 陣列長度
        n = len(nums)

        # 儲存最後一個負數的索引位置
        neg = -1 
        # enumerate: 拜訪 nums 同時取得索引 (i) 和對應的數值 (num)
        for i, num in enumerate(nums):
            if num < 0:
                # 如果 num 是負數，就更新 neg（找最後一個負數的索引）
                neg = i # index
            else:
                break

        ans = list()
        # i: 最後一個負數 index; j: 第一個非負數 index
        i, j = neg, neg + 1
        # 每次選擇較小數值加入陣列
        while i >= 0 or j < n: # 只要 i 或 j 還沒超出邊界，就繼續執行
            # 處理邊界條件
            if i < 0: # 代表負數部分已經遍歷完 ，指針直接移動到 j，處理剩下的另一半
                ans.append(nums[j] * nums[j])
                j += 1
            elif j == n: 
                ans.append(nums[i] * nums[i])
                i -= 1

            # 比較 nums[i]² 和 nums[j]²，選擇較小的加入 ans，並移動對應指針
            elif nums[i] * nums[i] < nums[j] * nums[j]:
                ans.append(nums[i] * nums[i])
                i -= 1
            else:
                ans.append(nums[j] * nums[j])
                j += 1
                
        return ans

:::

:::spoiler 官方題解二

class Solution:
    # 指针分别指向位置 0 和 n−1
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # 陣列長度
        n = len(nums)
        ans = [0] * n

        i, j, pos = 0, n-1, n-1 # pos 倒序由大到小儲存答案
        while i <= j:
            # 比較 nums[i]² 和 nums[j]²，選擇較大的加入 ans，並移動對應指針
            if nums[i] * nums[i] > nums[j] * nums[j]:
                ans[pos] = nums[i] * nums[i]
                i += 1
            else: 
                ans[pos] = nums[j] * nums[j]
                j -= 1
            pos -= 1

        return ans

:::

:::spoiler 靈神題解一
* reference: https://leetcode.cn/problems/squares-of-a-sorted-array/solutions/2806253/xiang-xiang-shuang-zhi-zhen-cong-da-dao-blda6/
* 概念：藉雙指針，從兩端開始，向中間合併。 ➡︎ 避免還需要計算要從中間哪個地方開始
* 程式：初始化空陣列 ans 和 其下標，雙指針 ➡︎ 計算兩端平方 ➡︎ 比較：選擇較大值填入 ans，直到陣列都填入數值

from typing import List # 导入 List（否则 Python 解释器会报 NameError: name 'List' is not defined）

class Solution:
    # 指针分别指向位置 0 和 n−1
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # 陣列長度
        n = len(nums)
        ans = [0] * n
        i, j = 0, n - 1  # 左右指針初始化

        # 答案陣列計算
        for p in range(n - 1, -1, -1):  # ans初始位置：n-1, 向左移：-1, 直到索引為0
            left = nums[i] * nums[i]  # 左指針平方值
            right = nums[j] * nums[j]  # 右指針平方值
            # 比較雙指針大小
            if left > right:
                ans[p] = left
                i += 1
            else:
                ans[p] = right
                j -= 1  # 修正：右指針應該向左移
        return ans

:::

:::spoiler ⭐️靈神題解二
* reference: https://leetcode.cn/problems/squares-of-a-sorted-array/solutions/2806253/xiang-xiang-shuang-zhi-zhen-cong-da-dao-blda6/
* 思路：先將左指針加上負號處理，在比較左右指針大小
* 優點：每次循環只要計算一次乘法
* 击败：97.81%

from typing import List # 导入 List（否则 Python 解释器会报 NameError: name 'List' is not defined）

class Solution:
    # 指针分别指向位置 0 和 n−1
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        i, j = 0, n-1 # 初始化左右指針: i, j

        # 左右指針數值比較，選擇較大平方，反序填入 ans
        # 處理答案陣列 
        for p in range(n-1, -1, -1): # 初始化 ｐ ans下標
            x, y = -nums[i], nums[j]
            # 比較左右指針大小
            if x > y:
                ans[p] = nums[i] * nums[i]
                i += 1
            else:
                ans[p] = nums[j] * nums[j]
                j -= 1
        return ans

:::