#双指针

有序数组的平方

题目

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

具体思路

使用双指针方法：

• 左右指针分别指向数组的两端。
• 比较左右指针对应元素的平方值，将较大的平方值放入结果数组的末尾。
• 移动指向较大平方值的指针，继续比较，直到左右指针相遇。
• 最终得到按非递减顺序排序的平方值数组。

具体代码

Java

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int[] res = new int[nums.length];
        int point = nums.length - 1;
        while(left != right){
            int leftnum = nums[left] * nums[left];
            int rightnum = nums[right] * nums[right];
            if(leftnum > rightnum){
                res[point] = leftnum;
                left++;
            }else{
                res[point] = rightnum;
                right--;
            }        
            point --;
        }
        res[point] = nums[left] * nums[left];
        return res;
    }
}

cpp

include <iostream>
include <vector>
using namespace std;

class Solution
{
public:
    vector<int> sortedSquares(vector<int> &nums)
    {
        int low = 0, high = nums.size() - 1;
        vector<int> res(nums.size(), 0);
        for (int k = res.size() - 1; k >= 0; k--)
        {
            int left = nums[low] * nums[low], right = nums[high] * nums[high];
            if (left > right)
            {
                res[k] = left;
                low++;
            }
            else
            {
                res[k] = right;
                high--;
            }
        }
        return res;
    }
};

int main()
{
    Solution s;
    vector<int> nums = {-4, -1, 0, 3, 10};
    vector<int> res = s.sortedSquares(nums);
    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i] << " ";
    }
    cout << endl;
    vector<int> nums1 = {-7, -3, 2, 3, 11};
    vector<int> res1 = s.sortedSquares(nums1);
    for (int i = 0; i < res1.size(); i++)
    {
        cout << res1[i] << " ";
    }
    cout << endl;
    return 0;
}

时间和空间复杂度

• 时间复杂度：O(n)，其中 n 是输入数组的长度。因为我们只需要遍历数组一次。
• 空间复杂度：O(n)，因为我们需要一个额外的数组来存储结果。