leet Code 977. Squares of a Sorted Array_network

[977. Squares of a Sorted Array]

[(https://leetcode.cn/problems/squares-of-a-sorted-array/)

暴力解法

• 对数组中每个元素平方后再排序

• 代码如下：

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

• 时间复杂度： O(n + nlogn)

  空间复杂度：O（1）

双指针

• 根据题意，数组内元素是按non-decreasing排列。因此，最大数必然要么在左要么在右，不可能在中间

• 故，我们设置 l = 0， r = nums.size() – 1 ，让i指向起始位置，而r指向最终位置，两边不断向中间移动

• 再者，我们创建一个与nums大小相同的新数组，让i指向数组的最终位置

• 若nums[ l ] * nums[ l ] < nums[ r ] * nums[ r ]，result[ i– ] = nums[ r ] * nums[ r ]

  若nums[ l ] * nums[ l ] > nums[ r ] * nums[ r ]，result[ i– ] = nums[ l ] * nums[ l ]

• 代码如下：

class Solution {public:    vector sortedSquares(vector& nums) {        int i = nums.size() - 1;        vectorresult( i + 1 );        for( int l = 0, r = nums.size() - 1; l <= r; )//最后需处理一个元素，因此为l <= r        {            if( nums[l] * nums[l] < nums[r] * nums[r] )            {                result[i--] = nums[r] * nums[r];                --r;            }            else            {                result[i--] = nums[l] * nums[l];                ++l;            }        }        return result;    }};

• 时间复杂度：O(n)

  空间复杂度：O(1)