沈阳企业网站设计制作,如何用手机创建网站,购物网站 缓存,专业网站设计联系给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 排序。
示例 1#xff1a;
输入#xff1a;nums [-4,-1,0,3,10]
输出#xff1a;[0,1,9,16,100]
解释#xff1a;平方后#xff0c;数组变为 …
给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
示例 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]提示
1 nums.length 104-104 nums[i] 104nums 已按 非递减顺序 排序 进阶
请你设计时间复杂度为 O(n) 的算法解决本问题 1. 暴力法
class Solution {
public:vectorint sortedSquares(vectorint nums) {for (int i 0; i nums.size(); i) {nums[i] nums[i] * nums[i];}sort(nums.begin(),nums.end());return nums;}
};
2. 双指针
可以发现数组本身就是有序的但是平方之后可能会无序因为负数平方之后变成了正数那么最大值还是只可能在最前面和最后面取到我们可以定义两个指针一个从前一个从后开始比较大小平方之后更大的加入到新数组的注意新数组是空数组我们从后往前加就不用最后再排序了。
class Solution {
public:vectorint sortedSquares(vectorint nums) {vectorint res(nums.size(),0);int k nums.size()-1;for(int first 0,last nums.size()-1;firstlast;){if(nums[first]*nums[first] nums[last]*nums[last]){res[k--] nums[last]*nums[last];last--;}else{res[k--] nums[first]*nums[first];first;}}return res;}
};
