目录
- 前言
- 算法题(LeetCode 977有序数组的平方)—(保姆级别讲解)
-
- 结束语
前言
本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!!
算法题(LeetCode 977有序数组的平方)—(保姆级别讲解)
力扣题目链接
分析题目
- 该数组为
非递减顺序
的顺序整数数组
- 返回的数组也需要按照
非递减
顺序排序
算法思想(重要)
这里主要讲解两种算法思想,分别是:
- 暴力解法
- 双指针法
暴力解法代码:
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;) {
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;
}
};
//时间复杂度是 O(n)
为了更能让大家了解暴力解法的算法思想,作者特意画了一张图供大家观看!!!
结束语
如果觉得这篇文章还不错的话,记得点赞 ,支持下!!!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)