[LeetCode 解題筆記] Squares of a Sorted Array

原題目網址：977. Squares of a Sorted Array

題目描述

給定一個由小到大排序的整數陣列 nums ，return 一個將其中每個元素平方後由小到大排序的新陣列。

解題思路

1. 由於 input array 為由小到大排序的陣列，取平方後，會有所變動的部分只有那些原本是負數的元素。（負數取平方會變正數）
2. 基於以上觀察可以實作出一個 linear time 的演算法：

• 維護兩個 pointer i 跟 j （i 指向最小元素， j 指向最大元素）
• 在 output 取平方後的值到新陣列的時候，從最後一個位置開始 output （意味從最大值開始 output）
• 每次 iteration 都比較 nums[i] 跟 nums[j] 取絕對值以後誰比較大，絕對值大者取平方後 output 到新陣列中，並且將 i 跟 j 做對應的移動。

以下為用 C 語言實作的程式碼：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int abs(int x) {
  return (x < 0) ? -x : x;
}

int* sortedSquares(int* nums, int numsSize, int* returnSize){
  int *new_nums = malloc(sizeof(int) * numsSize);
  *returnSize = numsSize;
  int i = 0;
  int j = numsSize - 1;
  for (int k = numsSize - 1; k >= 0; k--) {
    if (abs(nums[i]) > abs(nums[j])) {
      new_nums[k] = nums[i] * nums[i];
      i++;
    } else {
      new_nums[k] = nums[j] * nums[j];
      j--;
    }
  }
    
  return new_nums;
}