題目：

977. 有序數(shù)組的平方

難度簡單742收藏分享切換為英文接收動態(tài)反饋

給你一個按?非遞減順序?排序的整數(shù)數(shù)組?nums，返回?每個數(shù)字的平方?組成的新數(shù)組，要求也按?非遞減順序?排序。

?

示例 1：

輸入：nums = [-4,-1,0,3,10]輸出：[0,1,9,16,100]解釋：平方后，數(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?已按?非遞減順序?排序

?

進階：

• 請你設計時間復雜度為?O(n)?的算法解決本問題

第一種對法：

class?Solution?{

public:

????vector<int>?sortedSquares(vector<int>&?nums)?{

????????vector<int>?s(nums.size(),0);

????????int?first,last,index=nums.size()-1;

????????first=0;last=nums.size()-1;

????????while(first<=last){

????????????if(nums[first]*nums[first]>nums[last]*nums[last]){

????????????????s[index--]=nums[first]*nums[first];

????????????????first++;

????????????}else{

????????????????s[index--]=nums[last]*nums[last];

????????????????last--;

????????????}

????????}

????????return?s;

????}

};

創(chuàng)建一個新數(shù)組，用來存儲答案，在末尾和開頭分別放置一個指針，兩個指針相互靠近，每次比較將平方大的放進答案數(shù)組，最后返回；

時間復雜度O(n);

空間復雜度O(n);

雙指針算法