河北省电力建设第一工程公司网站,2017两学一做网站,wordpress 360加速插件,做淘宝客网站要申请什么题目
给你一个按 非递减顺序 排序的整数数组 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 104104 nums[i] 104nums 已按 非递减顺序 排序
思路
方法一 先求解再排序。
class Solution {
public:vectorint sortedSquares(vectorint A) {for (int i 0; i A.size(); i) {A[i] * A[i];}sort(A.begin(), A.end()); // 快速排序return A;}
}方法2牺牲空间来换取时间复杂度 思路既然起始时顺序是排好的只不过第一个位置的负的元素可能平方后可能是最大的也有可能是最后一个元素的平方后是最大的要排在最后。既然这样最大的数排在最后或者开头负数因此不会在中间。
1、定义一个新的数组result用来结果定义一个变量k指向result最后一个位置当有最大的数据筛选出来时每次把它移入到新数组组中。 2、定义两个“指针”i,j分别指向原数组nums的数组的起始位置和末尾位置。 3、如果num[i]*nums[i]nums[j]*nums[j]时说明起始位置的元素比较大。将其移入到新元素的末位置中同时使得k--i。 4、如果num[i]*nums[i]nums[j]*nums[j]时说明起始位置的元素比较小末尾元素比较大。将其移入到新元素的末位置中同时使得k--j--; 5、最后返回result数组即可。
代码实现
//方法2 i want to 武动乾坤 2023/08/08
class Solution {
public:vectorint sortedSquares(vectorint nums) {int knums.size()-1;//使得k指向result数组最后一个位置vectorint result(nums.size(),0);//定义result容器for(int i0,jnums.size()-1;ij;){//ij保证最后两个数据也能被比较加入新数组if(nums[i]*nums[i]nums[j]*nums[j]){//起始位置大result[k--]nums[i]*nums[i];//注意k--是先赋值再--//等同于result[k]nums[i]; k--;i;//指针向后移动}else{result[k--]nums[j]*nums[j];//注意k--是先赋值再--//等同于result[k]nums[i]*nums[i]; k--;j--;//指针向前移动}}return result;//返回新的结果集}};
