有序数组的平方(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;}
};