【leetcode】977. 有序数组的平方（squares-of-a-sorted-array）（双指针）[简单]

链接

https://leetcode-cn.com/problems/squares-of-a-sorted-array/

耗时

解题：9 min
题解：18 min

题意

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

思路

刚开始没有想清楚，直接上手写的，所以我的思路有点复杂 😦 。非常不建议用。

1. 数组中有正有负的时候，找到正负分割的地方，或者 0 的位置。然后用双指针。
2. 数组中元素非正，平方倒放。
3. 数组中元素非负，平方正放。

时间复杂度： O ( n ) O(n) O(n)

AC代码

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        vector<int> res;
        int n = A.size();
        if(A[0] < 0 && A[n-1] > 0) {
            int p, q;
            for(int i = 1; i < n; ++i) {
                if(A[i] == 0) {
                    p = i-1;
                    q = i+1;
                    res.push_back(0);
                    break;
                }
                if(A[i-1]*A[i] < 0) {
                    p = i-1;
                    q = i;
                    break;
                }
            }
            while(p >= 0 && q < n) {
                if(A[p]*A[p] <= A[q]*A[q]) {
                    res.push_back(A[p]*A[p]);
                    p--;
                }
                else {
                    res.push_back(A[q]*A[q]);
                    q++;
                }
            }
            while(p >= 0) {
                res.push_back(A[p]*A[p]);
                p--;
            }
            while(q < n) {
                res.push_back(A[q]*A[q]);
                q++;
            }
        }
        else if(A[0] < 0 && A[n-1] <= 0) {
            for(int i = n-1; i >= 0; --i) {
                int a = A[i];
                res.push_back(a*a);
            }
        }
        else {
            for(auto a : A) {
                res.push_back(a*a);
            }
        }
        return res;
    }
};