leetcode-有序数组的平方

有序数组的平方

题解：该题是对一个递增数组中的每个数字做平方和然后将结果重新按照递增顺序组成一个新的数组并返回

暴力解

思路很简单，就是对整个数组作循环，然后对数组内的每个数作平方和后再用排序算法重新排序，时间复杂度为O(N + nlogn)

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)。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        // 快慢指针
        // int len = nums.size();
        int k = nums.size() - 1;
        vector<int> result(nums.size(), 0);     // 创建一个大小和nums一致并用0初始化的数组
        int fast = nums.size()-1;
        int slow = 0;

        while(slow <= fast) {
            if(nums[slow] * nums[slow] < nums[fast] * nums[fast]) {
                result[k--] = nums[fast] * nums[fast];
                fast--;
            }
            else {
                result[k--] = nums[slow] * nums[slow];
                slow++;
            }
        }
        return result;
    }
};