Squares of a Sorted Array

Posted by chunyang on April 5, 2019

题目

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:

Input: [-4,-1,0,3,10]

Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]

Output: [4,9,9,49,121]

Note:

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

解法

算法复杂度 O(n),空间复杂度 O(n)。空间复杂度是由于需要存储返回的结果。

思路

直观解法,我们将数组进行重新排序,然后直接挨个计算平方,塞回到返回里面就可以了。这种解法并没有 利用数组原来就有序的特点,时间复杂度是 O(nlogn)。其实本质上数组分为三个部分:

  • 小于 0
  • 等于 0
  • 大于 0

我们其实需要做一个正负两部分的 merge,因为都是各自有序。负数从 0 往左,正数从 0 往右,按照绝对值 进行 merge 就可以了。(这里不一定有0, 从最后一个负数,第一个正数往两端走即可)

下面代码还可以优化,例如减少 abs 的调用;代码逻辑可以简单点(判断全是正数或者全是负数合为一个)

代码

class Solution {
private:
    /* used to sort according to abs of value in std::sort of stl */
    struct Comp {
        bool operator()(const int& lhs, const int& rhs) {
            int a = abs(lhs);
            int b = abs(rhs);
            if (a < b) {
                return true;
            } else {
                return false;
            }
        }
    };
public:
    vector<int> sortedSquares(vector<int>& A) {
        if (A.empty()) {
            return vector<int>();
        }
        vector<int> result;
        int length = A.size();
        if (A[0] < 0) {
            int first_neg = 0;
            while (first_neg < length && A[first_neg] < 0) ++first_neg;
            if (first_neg == length) {
                while (length > 0) {
                    result.push_back(A[length-1] * A[length - 1]);
                    --length;
                }
            } else {
                int first_pos = first_neg;
                --first_neg;
                while (first_neg >= 0 || first_pos < length) {
                    if (first_neg >= 0 && first_pos < length) {
                        auto a = A[first_pos];
                        auto b = abs(A[first_neg]);
                        result.push_back(a > b ? b * b: a * a);
                        a > b ? --first_neg : ++first_pos;
                    } else if (first_neg >= 0) {
                        auto b = abs(A[first_neg]);
                        result.push_back(b * b);
                        --first_neg;
                    } else if (first_pos < length) {
                        auto a = A[first_pos];
                        result.push_back(a*a);
                        ++first_pos;
                    }
                }
            }
        } else {
            int i = 0;
            while (i < length) {
                result.push_back(A[i] * A[i]);
                ++i;
            }
        }
        /* copy(A.begin(), A.end(), ostream_iterator<int>(cout, ", ")); */
        return result;
    }
};

本文完