LeetCode 977 題：有序數組的平方 (Squares of a Sorted Array)

LeetCode 第977題要求給定一個按非降序排列的整數數組 nums，返回每個數字的平方并按升序排列。

---

題目描述

給定一個整數數組 nums，它按非降序排列（即 nums[i] <= nums[i+1]），請返回該數組中每個數字的平方并按升序排列。

示例 1：

輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]

示例 2：

輸入：nums = [-7,-3,2,3,11]
輸出：[4,9,9,49,121]

---

解題思路

1. 雙指針法：

   • 因為輸入數組已經按非降序排列，所以數組中的元素的平方值并不會有嚴格的順序。
   • 數組的平方值可能有兩個不同的極端值：
     • 負數的平方會變大，可能會出現在數組的左側。
     • 正數的平方會變小，可能會出現在數組的右側。

2. 雙指針：

   • 我們可以使用兩個指針，一個從數組的左端開始，另一個從右端開始。比較這兩個指針指向的元素的平方值，較大的平方值將放在結果數組的末尾。
   • 將結果數組的指針逐漸向中間靠攏，直到所有的平方值都被放入結果數組。

3. 復雜度分析：

   • 時間復雜度：$O(n)$，其中 $n$ 是數組 nums 的長度。我們只遍歷數組一次。
   • 空間復雜度：$O(n)$，我們使用額外的數組存儲結果。

---

C語言代碼實現

以下是使用雙指針法的代碼實現：

#include <stdio.h>
#include <stdlib.h>int* sortedSquares(int* nums, int numsSize, int* returnSize) {int left = 0, right = numsSize - 1;*returnSize = numsSize;int* result = (int*)malloc(sizeof(int) * numsSize);int index = numsSize - 1; // 結果數組的指針從末尾開始while (left <= right) {if (abs(nums[left]) > abs(nums[right])) {result[index--] = nums[left] * nums[left];left++;} else {result[index--] = nums[right] * nums[right];right--;}}return result;
}int main() {int nums[] = {-4, -1, 0, 3, 10};int returnSize;int* result = sortedSquares(nums, 5, &returnSize);printf("Result: ");for (int i = 0; i < returnSize; i++) {printf("%d ", result[i]);}printf("\n");free(result); // 釋放內存return 0;
}

---

逐行解釋代碼

函數 sortedSquares

int left = 0, right = numsSize - 1;
*returnSize = numsSize;
int* result = (int*)malloc(sizeof(int) * numsSize);

• 初始化左右指針 left 和 right，分別指向數組的起始和末尾。
• returnSize 保存結果數組的大小，即 numsSize。
• 使用 malloc 動態分配內存給結果數組 result，其大小為輸入數組 nums 的長度。

---

int index = numsSize - 1; // 結果數組的指針從末尾開始

• index 指針從結果數組的末尾開始，這樣可以確保我們從最大值開始填充數組。

---

while (left <= right) {if (abs(nums[left]) > abs(nums[right])) {result[index--] = nums[left] * nums[left];left++;} else {result[index--] = nums[right] * nums[right];right--;}
}

• 使用 while 循環，直到 left 和 right 指針交匯。
• 比較 nums[left] 和 nums[right] 的絕對值：
  • 如果 nums[left] 的絕對值大于 nums[right]，則將 nums[left] 的平方放入 result 數組的末尾，并將 left 指針向右移動。
  • 否則，將 nums[right] 的平方放入 result 數組的末尾，并將 right 指針向左移動。
• 每次操作后，index 指針向前移動，以確保將平方值存入正確的位置。

---

return result;

• 返回結果數組 result，它包含按升序排列的平方值。

---

測試代碼 main

int nums[] = {-4, -1, 0, 3, 10};
int returnSize;
int* result = sortedSquares(nums, 5, &returnSize);printf("Result: ");
for (int i = 0; i < returnSize; i++) {printf("%d ", result[i]);
}
printf("\n");free(result); // 釋放內存

• 定義一個測試用例 nums = {-4, -1, 0, 3, 10}。
• 調用 sortedSquares 函數獲取結果。
• 打印輸出結果數組。
• 使用 free 釋放 malloc 動態分配的內存。

---

測試結果

運行代碼后輸出：

Result: 0 1 9 16 100

---

復雜度分析

1. 時間復雜度：$O(n)$

   • 我們只遍歷一次數組，left 和 right 每次向內移動一次，最終會遍歷整個數組。

2. 空間復雜度：$O(n)$

   • 我們使用了一個額外的數組 result 來存儲平方后的結果。