代码随想录算法训练营第一天 | 数组理论基础，977.有序数组平方结果再排序

题目说明：数组本身有序，且元素值可通用负数（注意不是复数），平方结果值还能以有序方式排列

标准想法就是在原数组基础上，把所有元素求平方结果值

再将这个有新结果值的数组，进行排序

生成平方结果值，是一个$O(n)$的复杂度，再进行排序，使用快排也需要$O(\log n)$的复杂度

总体来说，复杂度是要加一个尾巴的，如何去除这个尾巴呢，大师说用双指针

为什么用双指针，因为我们发现，在原数组中，绝对值最大的数是排列在数组的左右两侧的，这是绝对的

而两端数字的平方值都是最大的

使用两个下标变量，分别指向数组两端，从两端向中间递进，就可以得到最大值到最小值的序列

因为要覆盖，所以要用一个新数组，来保存这个新序列，空间复杂度只能放弃优化，这也是此算法的局限

#include <iostream>
#include <vector>class Solution {
public:std::vector<int> sortedSquares(std::vector<int>& nums) {int len = nums.size();std::vector<int> res;res.resize(len);for (int i = 0, j = len - 1, k = len - 1; i <= j; k--) {if (nums.at(i) * nums.at(i) > nums.at(j) * nums.at(j)) {res.at(k) = nums.at(i) * nums.at(i);++i;}else {res.at(k) = nums.at(j) * nums.at(j);--j;}}return res;}
};
int main()
{std::vector<int> nums {-7, -3, 2, 3, 11};Solution s;std::vector<int> new_nums = s.sortedSquares(nums);for (auto it = new_nums.begin(); it != new_nums.end(); ++it)std::cout << *it << " ";std::cout << std::endl;return 0;
}

虽然有些局限，但算法的精巧与思维的灵动，还是让人叹为观止的

汇总