题目描述
给你一个按非递减顺序排序的整数数组nums,返回每个数字的平方组成的新数组,要求也按非递减顺序 排序。
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
解题思路
- 原数组就是一个非递减的数组,所以经过平方后的数组,最大值就在两端产生
- 双指针方法,比较第一个和最后一个,选出最大的
- 创建一个新数组,用来存储每回比较选出的最大值
代码
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int k = nums.size() - 1; //数组最后一个下标
vector<int> result(nums.size(),0); //创建一个和nums同长度的数组
for(int i = 0, j = nums.size() - 1; i <= j;){ //循环条件必须有等号,不然最后一个数据不会进行运算,也就不能装到结果数组中去
if(nums[i]*nums[i ]> nums[j]*nums[j]){
result[k] = nums[i] * nums[i];
k--;
i++;
}
else{
result[k] = nums[j] * nums[j];
k--;
j--;
}
}
return result;
}
};
注意:其中循环条件必须要有=,不然最后一个数据不会进行运算,也就不能装到结果数组中去
其他思路
先平方,后进行排序
标签:平方,nums,result,数组,排序,lc.977,size From: https://www.cnblogs.com/wangshoutong/p/17169333.html