leetcode-977 Squares of a Sorted Array

977. Squares of a Sorted Array

Description

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

1
2
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

1
2
Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A is sorted in non-decreasing order.

Analyse

输入一个非递减的序列，输出这个序列的平方的非递减排序

主要考虑之前的负数平方后会使排序改变，先将整个序列求绝对值再排序，然后输出序列的平方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> sortedSquares(vector<int>& A) {
    for(int i = 0; i < A.size(); i++)
    {
        A[i] = abs(A[i]);
    }

    sort(A.begin(), A.end());

    for(int i = 0; i < A.size(); i++)
    {
        A[i] = A[i] * A[i] ;
    }
    return A;
}