代码随想录算法训练营第二天 | 题目1(LeetCode 977.有序数组的平方）

老实说，文章里面有些文字可能不是特别严谨，但是我感觉更加容易理解🐶

欢迎大家指出我的问题😊

欢迎大家指出我的问题😊

欢迎大家指出我的问题😊

原题链接https://link.csdn.net/target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fsquares-of-a-sorted-array%2Fsubmissions%2F

这个题其实不难，但是有一些细节问题值得学习（我感觉）👍

这是Carl哥的分享：代码随想录 (programmercarl.com)

🚥🚥🚥🚥🚥🚥

⭐方法1

暴力解法

时间复杂度：O(n+nlogn)也可以说是O(nlogn)

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

这是值得注意的地方（对于小白而言）

注意sort里面是nums.begin()  nums.end()

⭐方法2————注意题目中的数组是有序的

双指针算法

时间复杂度：O(n)

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

有一些值得注意的地方（请看图片）

🍔 vector<int>result(A.size(),0)的作用

定义了一个新数组，并且初始化为0,长度与数组A相同

因为原数组使用了vector，所以result也要定义为vector(我感觉）

🏳️‍🌈🏳️‍🌈🏳️‍🌈🏳️‍🌈🏳️‍🌈🏳️‍🌈🏳️‍🌈🏳️‍🌈

下面再附上c语言代码图片，是看了Carl哥的分享，感觉有一些细节值得注意

————————————————

版权声明：本文为CSDN博主「在下 小吉」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/m0_72853403/article/details/128654646

🚥🚥🚥🚥🚥🚥

That's all,thank you!

欢迎大家指出我的问题😊

欢迎大家指出我的问题😊

欢迎大家指出我的问题😊