题目描述
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
样例
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]
算法1
(暴力排序) $O(n + nlogn)$
将数组中每个数平方之后,再排个序
时间复杂度
O(n + nlogn)
依次完成平方操作,时间复杂度O(n);
快时间复杂度O(nlogn)
参考文献
Java 代码
class Solution {
public int[] sortedSquares(int[] nums) {
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
ans[i] = nums[i] * nums[i];
}
Arrays.sort(ans);
return ans;
}
}
Python 代码
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
return sorted(num * num for num in nums)
算法2
(双指针法) $O(n)$
新建一个长度为n(len(nums))的数组A【n】,由于给定的数组为非递减数组,可知元素平方最大值一定来自与头尾(左右)两端,每次比较头尾(左右)两端平方后的数值,将较大的数值赋值给数组A的末端n-1处,并让n -=1(n–),同时跟新头尾(左右)两端坐标
时间复杂度
python 代码
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n=len(nums)
A=[-1]*n
n -=1
left,right=0,len(nums)-1
while left<=right:
if nums[left]**2<nums[right]**2:
A[n]=nums[right]**2
n -=1
right -=1
else:
A[n]=nums[left]**2
n -=1
left +=1
return A
Java 代码
class Solution {
public int[] sortedSquares(int[] nums) {
int left=0;
int high=nums.length-1;
int[] nums_2=new int[nums.length];
int k=nums.length-1;
while(left<=high){
if(nums[left]*nums[left]>nums[high]*nums[high]){
nums_2[k--]=nums[left]*nums[left++];
}else{
nums_2[k--]=nums[high]*nums[high--];
}
}
return nums_2;
}
}