|
不是最好的解法，但是易懂。
题目：977.有序数组的平方
难度：简单
给你一个按?非递减顺序?排序的整数数组?nums，返回?每个数字的平方?组成的新数组，要求也按?非递减顺序排序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
示例
输入：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：简单暴力，直接把每个元素平方然后排序。sort是真的方便。
vector<int> sortedSquares(vector<int>& nums) {
int i;
for (i = 0; i < nums.size(); i++){
nums[i] *= nums[i];
}
sort(nums.begin(),nums.end());
return nums;
}
思路2：我们可以发现在所给整数有正有负的情况下，两边一定可以找到可以得到最大的平方值的数，因此可以使用两个变量，从两边向中间每次选出一个最大值，使用头插法插入新申请的vector容器中。
但是，重点。。这个办法居然要比思路1的简单方法用时多很多，直接被碾压。建议直接跳过。
反面教材献上。。。毕竟我只是个菜dog
考虑到剩余元素可能全为非负或非正的情况，可使这个笨办法稍微聪明一丢丢。
涉及vector容器头插法可参考：https://blog.csdn.net/qq_44361706/article/details/118223265?spm=1001.2014.3001.5501
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector <int> v;
int l = 0,r = nums.size()-1,i;
while(r > l){
if(nums[l] >= 0){ //判断剩余数是否全为非负
for(i = r; i >= l; i--){
v.insert(v.begin(), nums[i] * nums[i]);
}
return v;
}else if(nums[r] <= 0){ //判断剩余数是否全为非正
for(i = l; i <= r; i++){
v.insert(v.begin(), nums[i] * nums[i]);
}
return v;
}else{ //两数一定一正一负 正数加上负数来比较绝对值大小
if(nums[r] + nums[l] < 0){ //负数绝对值大于正数
v.insert(v.begin(), nums[l] * nums[l]);
l++;
}else if(nums[r] + nums[l] > 0){ //正数大于负数绝对值
v.insert(v.begin(), nums[r] * nums[r] );
r--;
}else { //正数等于负数绝对值
v.insert(v.begin(), nums[l] * nums[l]);
v.insert(v.begin(), nums[l] * nums[l]);
l++;
r--;
}
}
}
if(r==l){
v.insert(v.begin(), nums[r] * nums[r]);
}
return v;
}
};
部分测试用例
输入：
[-4,-1,0,3,10]
[-7,-3,2,3,11]
[0,2]
预期结果：
[0,1,9,16,100]
[4,9,9,49,121]
[0,4]
|