力扣977. 有序数组的平方（双指针、归并）
给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
示例 1：
输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]
示例 2：
输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。
双指针、归并
思路：
- 利用已排序的特点，找到负数与非负的分界线pos
- pos两边，左右双指针left和right
- 归并排序
复杂度分析
-
时间复杂度：O(n)，其中 n 是数组 A 的长度。
-
空间复杂度：O(1)。
#include <iostream>
#include<vector>
#include <math.h>
using namespace std;
class Solution {
public:vector<int> sortedSquares(vector<int>& A) {int n=A.size();vector<int> result;if(n==0)return result;//先找出绝对值最少的那一个，分界线int pos=0;for (int i=1; i<n; i++) {if (abs(A[i])<abs(A[i-1])) {pos=i;}}int left=pos-1;int right=pos+1;result.push_back(pow(A[pos],2));//归并排序while (left>=0 && right<=n-1) {int leftpow=pow(A[left],2);int rightpow=pow(A[right],2);if (leftpow>=rightpow) {result.push_back(rightpow);right++;}if (leftpow<rightpow) {result.push_back(leftpow);left--;}}while (left>=0) {int leftpow=pow(A[left],2);result.push_back(leftpow);left--;}while (right<=n-1) {int rightpow=pow(A[right],2);result.push_back(rightpow);right++;}return result;}
};
int main(int argc, const char * argv[]) {// insert code here...vector<int>A;A.push_back(-4);A.push_back(-1);A.push_back(0);A.push_back(3);A.push_back(10);Solution s;auto result=s.sortedSquares(A);for (int i=0; i<result.size(); i++) {std::cout <<result[i]<<" ";}std::cout << "\nHello, World!\n";return 0;
}