五月集训——Day3：977

• • ***、题目链接
  • 一、题目
  • • 1、题目描述
    • 2、基础框架
  • 二、解题报告
  • • 1、思路分析
    • 2、时间复杂度
    • 3、代码详解
  • 三、写在最后

        Day3：Leetcod 977. 有序数组的平方

        给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

        样例输入： nums = [-4,-1,0,3,10]；
        样例输出： [0,1,9,16,100]。
        解       释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]。

• C++给出的代码框架如下：

class Solution {
public:
    vector sortedSquares(vector& nums) {
    }
};

       ( 1 ) (1) (1) 由于先平方使用 sort 函数，其时间复杂度为 O ( n l o g n ) O(nlog_n) O(nlogn​) ，要实现 O ( n ) O(n) O(n) ，需要使用双指针；
       ( 2 ) (2) (2) 定义两个指针，一个从前遍历，一个从后遍历，比较其平方的大小，将大的存放到新建的字符串末尾；

       O ( n ) O(n) O(n) ， n n n 为字符串长度；

class Solution {
public:
    vector sortedSquares(vector& nums) {
        int left, right;
        int n = nums.size() - 1;
        vector ret(n + 1);
        for(int i = 0, j = n, pos = n; i <= j;){
            left = nums[i] * nums[i];
            right = nums[j] * nums[j];

            if(left > right){
                ret[pos] = left;
                ++i;
            } else {
                ret[pos] = right;
                --j;
            }
            --pos;
        }

        return ret;
    }
};

          当我们发现使用库函数的时候无法达到应有的时间复杂度，我们应该想办法在内部自己实现该函数。