问题描述
给定一个升序排列的整形数组，要求返回每个元素计算平方值之后的数组，且升序排列。
- 栗子 1：
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
- 栗子 2：
Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]
注意：
1. 1 <= A.length <= 10000
2. -10000 <= A[i] <= 10000
3. A 升序排列
想看英文的戳这里：原题地址
解题思路
大脑中最直观闪现的解法
相信大家最先想到的方法，就是分别计算出每个元素的平方值后，然后进行排序，解题完毕，然后大笑一声 哈哈哈，这题这么简单。
swift 代码提交，发现速度并不快，faster than 60%。
func sortedSquares(_ A: [Int]) -> [Int] {
var squares = [Int]()
for n in A {
squares.append(n * n)
}
// 排序
return squares.sorted()
}
暗藏玄机
第一种解法，其实并没有用到题目中给的条件，A 是升序排列的。
下面我们来简单分析一下。
假设 A = [0, 3, 10]，全为正数，那么按原顺序就好；
假设A = [-4, -3, -2]，全为负数，负数越小，平方和越大，那么倒序遍历，刚好是升序的；
假设A = [-4, -3, -2, 0, 3, 10]，既有负数，也有正数，并且负数是有序的，正数也是有序的，于是可以想到将两个有序数组合并成一个有序的数组。
负数数组：[-4, -3, -2]，从后往前遍历，使用其绝对值进行比较。
正数数组：[0, 3, 10]，从前往后遍历。
完整代码如下：
func sortedSquares_2(_ A: [Int]) -> [Int] {
// 因为 A 已经排好序，找到前面的负数部分从后遍历，和后面的正数部分从前遍历，进行合并
var negArray = [Int]()
var result = [Int]()
var i = 0
// 负数数组
while i < A.count {
if A[i] < 0 {
negArray.append(A[i])
i += 1
} else {
break
}
}
var j = negArray.count - 1
while j >= 0, i < A.count {
if abs(negArray[j]) < A[i] {
// 加入数组
result.append(negArray[j] * negArray[j])
j -= 1
} else {
result.append(A[i] * A[i])
i += 1
}
}
while j >= 0 {
result.append(negArray[j] * negArray[j])
j -= 1
}
while i < A.count {
result.append(A[i] * A[i])
i += 1
}
return result
}
