977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
请你设计时间复杂度为 O(n) 的算法解决本问题
示例1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
解题方法一：双指针
class Solution {
func sortedSquares(_ nums: [Int]) -> [Int] {
var lastNeg = -1
for i in 0..<nums.count {
if nums[i] < 0 {
lastNeg = i
} else {
break
}
}
var left = lastNeg
var right = lastNeg + 1
var result = [Int]()
while left >= 0 || right < nums.count {
if left < 0 {
result.append(nums[right] * nums[right])
right += 1
} else if right >= nums.count {
result.append(nums[left] * nums[left])
left -= 1
} else if nums[left] * nums[left] < nums[right] * nums[right] {
result.append(nums[left] * nums[left])
left -= 1
} else {
result.append(nums[right] * nums[right])
right += 1
}
}
return result
}
}
解题思路:
由于数组是有序递增的，所以我们可以把数组分为两部分：负数部分和非负数部分。
负数部分平方后是递减的，非负数部分平方后是递增的。这样我们就可以使用双指针的方法来解决本题。定义左边的指针指向最后一个负数，同时定义右边指针指向第一个非负数。两个指针分别向左右两边遍历滑动，判断当前左右指针指向的元素平方后的大小，然后把小的那个添加到结果数组中。
需要注意处理和验证各种边界情况：
- 都是负数
- 都是非负数
- 左边指针或者右边指针已经到边界，剩余的另一个指针如果处理。
复杂度分析
- 时间复杂度：
O(n)，其中n是数组nums的长度。 - 空间复杂度：
O(1)。
解题方法二：双指针
class Solution {
func sortedSquares(_ nums: [Int]) -> [Int] {
var result = [Int](repeating: -1, count: nums.count)
var left = 0
var right = nums.count - 1
var pos = right
while left <= right {
let lValue = nums[left] * nums[left]
let rValue = nums[right] * nums[right]
if lValue < rValue {
result[pos] = rValue
right -= 1
} else {
result[pos] = lValue
left += 1
}
pos -= 1
}
return result
}
}
解题思路
同样地，我们可以使用两个指针分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择绝对值较大的那个放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况。
复杂度分析
- 时间复杂度：
O(n)，其中n是数组nums的长度。 - 空间复杂度：
O(1)。