977-有序数组的平方

LeetCode 977. Squares of a Sorted Array

LeetCode-977

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

method: 双指针

因为一个区间的平方，最大值肯定是在两边，所以用双指针从两边向中间遍历

结果数组从后往前插值

vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n);
    int cnt = n - 1;
    int l = 0, r = n - 1;
    while (l <= r) {    // 最后指向同一个元素也要算
        if (nums[l] * nums[l] < nums[r] * nums[r]) {
            res[cnt--] = nums[r] * nums[r];
            r--;
        }
        else {
            res[cnt--] = nums[l] * nums[l]; 
            l++;
        }
    }
    return res;
}

时间复杂度：$O(n)$
如果算完平方后再排序，时间复杂度是$O(n + nlogn)$