博客

排序平方

题目：给你一个按非递减顺序排序的整数数组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]

分析：数组的中间可能出现最小值，往两端逐渐变大，可以使用双指针从两端往中间移动

#include <vector>
#include <iostream>
using namespace std;

class Solution{
public:
    vector<int> sortedSquares(vector<int>& A){
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        int i = 0;
        int j = k;
        while (i <= j){
            if (A[i] * A[i] <= A[j] * A[j]){
                result[k--] = A[j] * A[j];
                j--;
            }else{
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};

int main(){
    vector<int> nums = {-9,-6,-5,-2,0,1,2,4,5,6,6,6,6,6,8,9};
    Solution s;
    vector<int> res = s.sortedSquares(nums);
    for (int i = 0; i < res.size(); i++){
        cout << res[i] << endl;
    }
}