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

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

題目描述

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

解題思路

  1. 由於 input array 為由小到大排序的陣列,取平方後,會有所變動的部分只有那些原本是負數的元素。(負數取平方會變正數)
  2. 基於以上觀察可以實作出一個 linear time 的演算法:
  • 維護兩個 pointer iji 指向最小元素, j 指向最大元素)
  • 在 output 取平方後的值到新陣列的時候,從最後一個位置開始 output (意味從最大值開始 output)
  • 每次 iteration 都比較 nums[i]nums[j] 取絕對值以後誰比較大,絕對值大者取平方後 output 到新陣列中,並且將 ij 做對應的移動。

以下為用 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;
}
Show Comments