有序数组的平方(leetcode 977)

一个数组，返回一个所有元素的平方之后依然是一个有序数组。（数组中含负数）

解法一：暴力解法

        所有元素平方后再使用快速排序法重新排序，时间复杂度为O(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;
    }
};

解法二：双指针

        思路：最大数一定在这个数组的两边，不可能在中间。利用两个指针从两边逐步向中间靠拢的过程，得到一个由大到小的数组。得到由小到大的数组，就是在更新新的数组时，下标由大到小来进行更新。

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