原題目網址:977. Squares of a Sorted Array
題目描述
給定一個由小到大排序的整數陣列 nums
,return 一個將其中每個元素平方後由小到大排序的新陣列。
解題思路
- 由於 input array 為由小到大排序的陣列,取平方後,會有所變動的部分只有那些原本是負數的元素。(負數取平方會變正數)
- 基於以上觀察可以實作出一個 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;
}