977. 有序数组的平方 C++

一、题目链接

链接: 977. 有序数组的平方

二、参考代码

简单思路：赋值给新的数组然后排序

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

    }
};

新思路：双指针，一个指针从数组的开始，另一个指针从数组的末尾，比较两个指针对应的元素的绝对值，然后将较大的那个元素的平方放到结果数组的末尾，然后移动指针，直到两个指针相遇。这样可以保证结果数组是有序的，并且时间复杂度为 O(n)。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> out(n, 0);
        int left = 0, right = n - 1, pos = n - 1;
        
        while (left <= right) {
            if (abs(nums[left]) > abs(nums[right])) {
                out[pos] = nums[left] * nums[left];
                left++;
            } else {
                out[pos] = nums[right] * nums[right];
                right--;
            }
            pos--;
        }
        
        return out;
    }
};

三、所思所悟

提供的双指针法适用于非递减数组，因为它依赖于绝对值较大的数在数组的两端这一特性。
如果数组不是非递减的，我们需要使用不同的方法来确保结果数组是有序的。

对于任意数组，我们仍然可以使用排序的方法，但是需要先对数组中的每个元素进行平方，然后再进行排序。这种方法的时间复杂度是 O(n^2) 的操作加上 O(n log n) 的排序操作，即 O(n log n)。