Task

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

  • 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.

Solution

  • 使用迭代器it向结果数组中写入值，从右往左写（从大往小）
  • 使用双指针，指针pl从数组A左侧向右走，指针pr从数组A右侧向左走
    • 当*pl的绝对值更大时，it向结果数组中写入其平方，并将pl向右移
    • 当*pr的绝对值更大时，it向结果数组中写入其平方，并将pr向左移
  • 时间复杂度：只需遍历一次，O(n)
  • 空间复杂度：除储存结果的数组外只用了3个指针，O(1)
  • 实现：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Runtime: 68 ms, faster than 84.10% of C++ online submissions for Squares of a Sorted Array.
// Memory Usage: 27.1 MB, less than 5.40% of C++ online submissions for Squares of a Sorted Array.
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        //双指针
        auto l=A.begin();
        auto r=A.end()-1;
        vector<int> B;
        //左边指针小于等于右边指针时，继续算
        while(l<=r){
            if(abs(*l)>=abs(*r))
                B.push_back(pow(*l++,2));
            else{
                B.push_back(pow(*r--,2));
            }
        }
        //反转
        reverse(B.begin(),B.end());
        return B;
    }
};