給你一個(gè)按 非遞減順序 排序的整數(shù)數(shù)組 nums，返回 每個(gè)數(shù)字的平方 組成的新數(shù)組周拐，要求也按 非遞減順序 排序凰兑。
示例 1：
輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋?zhuān)浩椒胶螅瑪?shù)組變?yōu)?[16,1,0,9,100]
排序后罕容，數(shù)組變?yōu)?[0,1,9,16,100]
示例 2：
輸入：nums = [-7,-3,2,3,11]
輸出：[4,9,9,49,121]
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非遞減順序 排序
進(jìn)階：
請(qǐng)你設(shè)計(jì)時(shí)間復(fù)雜度為 O(n) 的算法解決本問(wèn)題
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有锦秒。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處旅择。
看到這個(gè)問(wèn)題就想使用 in-place 算法生真，然后再結(jié)合雙指針的運(yùn)用來(lái)解決這個(gè)問(wèn)題沉噩，但是總是會(huì)遇到問(wèn)題，看了看之前的算法都又開(kāi)辟了一個(gè)新數(shù)組然后又借助了一個(gè)新的指示變量去在新數(shù)組里面進(jìn)行分配數(shù)據(jù)柱蟀。
** In-Place 半成品
vector<int> sortedSquares(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while( left <= right ){
int leftSquire = nums[left] * nums[left];
int rightSquire = nums[right] * nums[right];
if( leftSquire > rightSquire ){
int tmp = nums[right];
nums[right] = leftSquire;
nums[left] = tmp;
}else{
nums[right] = rightSquire;
}
right--;
}
return nums;
}
我感覺(jué)我還能再試一試
分析一下 in-place 方式為寫(xiě)不出來(lái)這個(gè)排序川蒙？
對(duì)于直接在原數(shù)據(jù)進(jìn)行修改的話會(huì)打亂原數(shù)據(jù)的順序，有點(diǎn)像歸并排序长已，都是建立在原數(shù)據(jù)是有序的前提之下的畜眨。進(jìn)而in-place 方式不可行。
非In-place 解法
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int left = 0, right = nums.size()-1, index = nums.size()-1;
vector<int> res(nums.size(), 0);
while(left <= right){
if( getAbs(nums[left]) > getAbs(nums[right])){
res[index--] = nums[left] * nums[left];
left++;
}else{
res[index--] = nums[right] * nums[right];
right--;
}
}
return res;
}
int getAbs(int x){
return x < 0 ? -x : x;
}
};
總結(jié)一波术瓮，
這個(gè)問(wèn)題的解決思路是通過(guò)比較兩端的值來(lái)確定最終結(jié)果數(shù)組的中最大值的康聂，因?yàn)榻Y(jié)果數(shù)組中的值是原數(shù)組元素的平方，并且負(fù)數(shù)越小平方值越大胞四，所以最大值一定會(huì)在原數(shù)組的兩端中出現(xiàn)恬汁。因此利用雙指針的算法就是通過(guò)兩端的指針不斷的向中心靠攏辜伟，從而得到一個(gè)有序的平方數(shù)組氓侧。又因?yàn)轭}目要求的是以非遞減的順序進(jìn)行排序，所以最終的結(jié)果數(shù)組是從末尾開(kāi)始填充結(jié)果數(shù)組元素游昼。
