問題描述
給定一個(gè)升序排列的整形數(shù)組将饺，要求返回每個(gè)元素計(jì)算平方值之后的數(shù)組卵史，且升序排列战转。
- 栗子 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 升序排列
想看英文的戳這里：原題地址
解題思路
大腦中最直觀閃現(xiàn)的解法
相信大家最先想到的方法，就是分別計(jì)算出每個(gè)元素的平方值后以躯，然后進(jìn)行排序槐秧，解題完畢，然后大笑一聲 哈哈哈忧设，這題這么簡(jiǎn)單刁标。
swift 代碼提交，發(fā)現(xiàn)速度并不快址晕，faster than 60%膀懈。
func sortedSquares(_ A: [Int]) -> [Int] {
var squares = [Int]()
for n in A {
squares.append(n * n)
}
// 排序
return squares.sorted()
}
暗藏玄機(jī)
第一種解法，其實(shí)并沒有用到題目中給的條件谨垃，A 是升序排列的启搂。
下面我們來簡(jiǎn)單分析一下。
假設(shè) A = [0, 3, 10]刘陶，全為正數(shù)胳赌，那么按原順序就好；
假設(shè)A = [-4, -3, -2]匙隔，全為負(fù)數(shù)疑苫，負(fù)數(shù)越小，平方和越大牡直，那么倒序遍歷缀匕，剛好是升序的；
假設(shè)A = [-4, -3, -2, 0, 3, 10]碰逸，既有負(fù)數(shù)乡小，也有正數(shù)，并且負(fù)數(shù)是有序的饵史，正數(shù)也是有序的满钟，于是可以想到將兩個(gè)有序數(shù)組合并成一個(gè)有序的數(shù)組胜榔。
負(fù)數(shù)數(shù)組：[-4, -3, -2]，從后往前遍歷湃番，使用其絕對(duì)值進(jìn)行比較夭织。
正數(shù)數(shù)組：[0, 3, 10]，從前往后遍歷吠撮。
完整代碼如下：
func sortedSquares_2(_ A: [Int]) -> [Int] {
// 因?yàn)?A 已經(jīng)排好序尊惰，找到前面的負(fù)數(shù)部分從后遍歷，和后面的正數(shù)部分從前遍歷泥兰，進(jìn)行合并
var negArray = [Int]()
var result = [Int]()
var i = 0
// 負(fù)數(shù)數(shù)組
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] {
// 加入數(shù)組
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
}
