跳转至

977 有序数组的平方

暴力做法

每个数平方之后再使用sort()排序

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            nums[i] *= nums[i];
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

时间复杂度: \(O(n + nlogn)\)

空间复杂度: \(O(n)\)

双指针法

观察数组,我们可以发现,位于数组两端的数的绝对值比中间大,因此它们的平方值也比中间大

因此我们可以从两端向中间遍历比较,将较大值放入新数组中

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        // 新数组末尾元素的位置
        int k = n - 1;
        // 新开一个数组
        vector<int> res(n, 0);
        // 左闭右闭区间[0,k]
        int left = 0, right = k;
        // 左闭右闭区间[left,right]
        while(left <= right){
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];
            if(leftSquare > rightSquare){
                // 题目要求数组非递减顺序,因此较大值放在数组末尾
                res[k--] = leftSquare;
                left++;
            }
            else{
                res[k--] = rightSquare;
                right--;
            }
        }
        return res;
    }
};

时间复杂度: \(O(n + nlogn)\)

空间复杂度: \(O(n)\)