題目
題目鏈接：https://leetcode.cn/problems/squares-of-a-sorted-array/
給你一個按 非遞減順序 排序的整數數組 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) {}
};
思路及代碼
雙指針
題目解析：
- 數組非遞減，
- 元素有正負 -> 元素平方后的結果（新數組）不是有序的，
- 輸出要求：數組非遞減，要有序
實現方法： 雙指針
- 指針
i指向起始位置，指針j指向終止位置 - 定義一個新數組
result，和nums數組大小一樣，讓k指向result數組的終止位置。 - 如果
nums[i]*nums[i] > nums[j]* nums[j],則result[k--] = nums[i] * nums[i] - 如果
nums[i]*nums[i] <= nums[j]* nums[j],則result[k--] = nums[j] * nums[j]
#include <vector>
#include <iostream>
using namespace std;class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int k = nums.size() - 1;vector<int> result(nums.size(), 0);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;}
};
// @lc code=endvoid printVector(vector<int>& nums){for(int i = 0; i < nums.size(); i++){cout << nums[i] << " ";}cout << endl;
}int main() {Solution obj;vector<int> vec = {-4,-3,-1,0,2,3,6,10};vector<int> res = obj.sortedSquares(vec);printVector(res);
}
時間復雜度：O(n)
總結
初始看到要使用雙指針，自己以為是使用雙指針來交換平方后的兩個元素，但正確的代碼思路并不是這樣的，正確的代碼思路更清晰明了
