思路
题目要求时间复杂度要为
O
(
n
)
O(n)
O(n),那就肯定不能用最简单的先赋值再排序的方法。
考虑原数组是一个有序的数组,即使平方后也是十分有序的一个数组。不妨假设原数组从负数到正数,就可以将其分为两部分:前面是平方递减的,后面是平方递增的(以0位分界)。
记得《算法》中说对于有序数组,归并排序是最快速的一种算法。因此这道题就可以考虑使用归并的思路进行解答。
使用两个指针分别指向原数组的首位元素和末位元素,这也是原数组平方后最大的两头(依旧不妨设其有负有正)。
从最大的两数开始比较。将较大的那一个数赋给结果数组的最后一位,再将次之的赋给前一位,以此类推(此过程无论原数组是否是有正有负都是正确的)。
代码
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
// 结果数组
vector<int> result(nums.size());
// 用归并的方法将这两个有序的数组归并为结果数组
// i, j用于分别从左右两端遍历原数组,k用于赋值新数组
int i = 0, j = nums.size() - 1, k = j;
int left, right; // 存储原数组的两个平方数
while (k >= 0) {
left = nums[i] * nums[i];
right = nums[j] * nums[j];
if (left > right) {
result[k] = left;
i++;
}
else {
result[k] = right;
j--;
}
k--;
}
return result;
}
};
总结
每个元素都只访问一次,时间复杂度是 O ( n ) O(n) O(n)。