題目

給你一個(gè)按 非遞減順序 排序的整數(shù)數(shù)組 nums，返回 每個(gè)數(shù)字的平方 組成的新數(shù)組，要求也按 非遞減順序 排序。
示例 1：
輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方后，數(shù)組變?yōu)?[16,1,0,9,100]
排序后，數(shù)組變?yōu)?[0,1,9,16,100]
示例 2：
輸入：nums = [-7,-3,2,3,11]
輸出：[4,9,9,49,121]
提示：
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10 ^4
nums 已按 非遞減順序 排序
進(jìn)階：
請(qǐng)你設(shè)計(jì)時(shí)間復(fù)雜度為 O(n) 的算法解決本問(wèn)題
來(lái)源：力扣（LeetCode）

解題思路

??題目十分的簡(jiǎn)單，遍歷求平方然后排序即可。

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:return sorted([i**2 for i in nums])

??這樣做的話是有一個(gè)條件沒(méi)有用上，那就是數(shù)組是非遞減的。進(jìn)一步的優(yōu)化可以在排序算法上，比如當(dāng)前數(shù)組已經(jīng)基本有序，那么利用插入排序就會(huì)有不錯(cuò)的提升，但是這樣仍然達(dá)不到進(jìn)階的意見。考慮插入排序，有效的操作也只是將負(fù)數(shù)的平方一個(gè)個(gè)插入有序的正數(shù)序列中，但其實(shí)負(fù)數(shù)序列也是非遞減的，所以負(fù)數(shù)序列和正數(shù)序列是兩個(gè)有序的序列，這樣的話就會(huì)是兩個(gè)有序的歸并段，兩個(gè)歸并段的排序時(shí)間復(fù)雜度便會(huì)降到O(n)。

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:if nums[0]>=0:return [i**2 for i in nums]for i in range(len(nums)):if nums[i]>=0:breakx=0y=0temp=[]while x<i and y<len(nums)-i:a=nums[0:i][::-1][x]**2b=nums[i:][y]**2if a>b:temp.append(b)y+=1else:temp.append(a)x+=1if x<i:return temp+[j**2 for j in nums[0:i][::-1][x:]]else:return temp+[j**2 for j in nums[i:][y:]]

??理論上時(shí)間復(fù)雜度低的話用時(shí)應(yīng)該更短，出現(xiàn)這種情況應(yīng)該是代碼出了一些問(wèn)題，可能還得進(jìn)行代碼上的優(yōu)化。

總結(jié)

以上是生活随笔為你收集整理的LeetCode简单题之有序数组的平方的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。