看完这篇文章你就彻底懂啦｛保姆级讲解｝-----（LeetCode刷题977有序数组的平方） 2023.4.20-Toy模板网

这篇具有很好参考价值的文章主要介绍了看完这篇文章你就彻底懂啦｛保姆级讲解｝-----（LeetCode刷题977有序数组的平方） 2023.4.20。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可，撰写本文章主要目的在于记录自己学习体会并分享给大家，全篇并不仅仅是复制粘贴，更多的是加入了自己的思考，希望读完此篇文章能真正帮助到您！！！

算法题（LeetCode 977有序数组的平方）—（保姆级别讲解）

力扣题目链接

看完这篇文章你就彻底懂啦｛保姆级讲解｝-----（LeetCode刷题977有序数组的平方） 2023.4.20

分析题目

该数组为非递减顺序的顺序整数数组
返回的数组也需要按照非递减顺序排序

算法思想（重要）

这里主要讲解两种算法思想，分别是：

暴力解法

双指针法

暴力解法代码：

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

//时间复杂度是 O(n + nlogn)

暴力算法的算法思想其实很简单，主要是分为两个步骤，分别是：

先在原有的基础上每个数组元素都进行平方。
在已经拼房的基础上使用快速排序进行排序即可。

双指针法（快慢指针法）代码：

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;) { // 注意这里要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;
    }
};