Description
給定一個按非遞減順序排列的整數陣列
nums，回傳每個數字平方後的結果，同樣按非遞減順序排列。
Example:
Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100]
Intuition#
陣列兩端的絕對值最大，用雙指標從兩端往中間靠攏，由大到小填入結果陣列。
- 因為有負數，平方後最大值一定在陣列的兩端
- 雙指標比較兩端的絕對值，較大的先放入結果陣列尾端
Approaches#
1: 排序法#
- 概念: 先全部平方，再排序
- 時間複雜度:
O(n log n) - 空間複雜度:
O(n)（排序用的空間）
排序法程式碼
class Solution {
fun sortedSquares(nums: IntArray): IntArray {
return nums.map { it * it }.sorted().toIntArray()
}
}⭐2: Two Pointers#
- 概念: 左右兩端指標，比較絕對值大小，從結果陣列尾端往前填入
- 時間複雜度:
O(n) - 空間複雜度:
O(n)（結果陣列）
class Solution {
fun sortedSquares(nums: IntArray): IntArray {
val n = nums.size
val result = IntArray(n)
var left = 0
var right = n - 1
var pos = n - 1
while (left <= right) {
val leftSq = nums[left] * nums[left]
val rightSq = nums[right] * nums[right]
if (leftSq > rightSq) {
result[pos] = leftSq
left++
} else {
result[pos] = rightSq
right--
}
pos--
}
return result
}
}🔑 Takeaways#
- Pattern: 雙指標合併（類似 merge sort 的合併步驟）
- 關鍵技巧: 已排序陣列含負數時，平方後的最大值在兩端，從大到小反向填入結果陣列是關鍵技巧