????????难度:简单
????????分类:数组
????????难度与分类由我所参与的培训课程提供,但需要注意的是,难度与分类仅供参考。以下内容均为个人笔记,旨在督促自己认真学习。
????????给你一个按非递减顺序(即递增)排序的整数数组 nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。
????????示例1:
????????输入:nums=[-4,-1,0,3,10]
????????输出:[0,1,9,16,100]
????????解释:平方后,数组变为[16,1,0,9,100], 排序后,数组变为[0,1,9,16,100]
????????示例2:
????????输入:nums=[-7,-3,2,3,11]
????????输出:[4,9,9,49,121]
????????额外要求: 请你设计时间复杂度为O(n)的算法解决本问题
????????这个问题的关键是将按非递减顺序排序的整数数组的元素平方后,按非递减顺序存储在新数组中。要解决这个问题,可以使用双指针的方法,时间复杂度为O(n)。
????????以下是解决问题的思路和步骤:
????????这个算法的关键点在于使用双指针,从原数组的两端向中间移动,根据平方值的大小选择左指针或右指针的值放入新数组。这样可以确保新数组中的值按非递减顺序排序。这个算法的时间复杂度是O(n),因为只需要一次遍历原数组。
????????理解这个算法可能会有些抽象,以下我将尝试提供更具体的步骤和示例来帮助你更好地理解:
????????假设我们有一个按非递减顺序排序的整数数组 nums
,如下所示:
nums = [-4, -1, 0, 3, 10]
????????我们首先创建一个新的数组 result
,用于存储平方后的结果,与 nums
数组的大小相同:
result = [0, 0, 0, 0, 0]
????????接下来,我们使用两个指针,一个指向 nums
数组的最小值(最左边的元素 -4
),另一个指向 nums
数组的最大值(最右边的元素 10
)。还有一个索引变量 index
初始化为新数组的最后一个位置(4)。
left = 0 right = 4 index = 4
????????然后,我们进入一个循环,直到 left
指针大于 right
指针。在循环中,我们执行以下步骤:
计算 left
指针元素的平方(例如,(-4) * (-4) = 16
)。
计算 right
指针元素的平方(例如,10 * 10 = 100
)。
比较左平方和右平方的大小。
result
数组的 index
位置,然后将 left
指针向右移动一位。result
数组的 index
位置,然后将 right
指针向左移动一位。每次循环结束后,index
向前移动一位。
????????重复以上步骤,直到 left
指针大于等于 right
指针。最终,result
数组将包含平方后的结果,按非递减顺序排序。
result = [0, 1, 9, 16, 100]
????????这个算法的关键是根据平方值的大小选择 left
指针或 right
指针的值放入 result
数组,并同时移动相应的指针。这样可以确保 result
数组中的值按非递减顺序排序。
?????????这种算法之所以能够实现按非递减顺序排序平方后的数组,是因为原始数组 nums
已经按非递减顺序排序。这个算法利用了两个指针,一个从数组的最小值开始,另一个从数组的最大值开始,然后向中间移动。下面解释为什么这个算法有效:
原始数组已排序: 由于原始数组 nums
已经按非递减顺序排序,因此数组中的元素可以分为负数和非负数两部分,其中非负数部分的平方值是递增的。这一点很关键,因为平方后的值仍然保持非递减顺序。
使用两个指针: 算法使用两个指针,一个指向原始数组的最小值(负数部分的开头),另一个指向最大值(非负数部分的结尾)。这两个指针向中间移动,保证了我们能够同时考虑到负数和非负数部分的平方值。
比较平方值大小: 在每一步中,算法比较了左指针元素的平方值和右指针元素的平方值,然后选择较大的平方值存储在新数组中。这个选择是为了确保新数组中的值按非递减顺序排序。
指针移动: 根据比较的结果,如果左平方值较大,那么左指针向右移动;如果右平方值较大,那么右指针向左移动。这样在每一步都选择了当前范围内的最大平方值,并将其放入新数组中。
索引递减: 为了确保新数组中的值按非递减顺序排序,使用一个索引变量从新数组的末尾向前移动。这确保了新数组中的较大平方值被放在正确的位置。
????????这个算法的本质是通过双指针,分别从原数组的两端向中间移动,每次选择当前指针所指元素的平方值中较大的一个,然后逆序填充到新数组中,从而得到按非递减顺序排序的平方结果。
????????总结来说,这个算法通过合理的双指针移动和平方值比较,充分利用了原始数组已排序的性质,使得新数组中的值按非递减顺序排序。这是一种非常高效的方法,时间复杂度为O(n)。
#include <cmath> // 包含C++标准库中的cmath头文件,用于平方操作
#include <iostream> // 包含C++标准库中的iostream头文件,用于输入输出
#include <vector> // 包含C++标准库中的vector头文件,用于使用向量容器
using namespace std; // 使用C++标准库的std命名空间
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size(); // 获取输入数组的大小
vector<int> result(n); // 创建一个新的整数向量,用于存储平方后的结果
int left = 0, right = n - 1; // 初始化左右指针,分别指向数组的第一个和最后一个元素
int index = n - 1; // 从新数组的末尾开始填充
while (left <= right) { // 进入循环,直到左指针大于右指针
int left_square = pow(nums[left], 2); // 计算左指针元素的平方
int right_square = pow(nums[right], 2); // 计算右指针元素的平方
if (left_square >= right_square) { // 如果左平方大于等于右平方
result[index] = left_square; // 将左平方值存入新数组
left++; // 移动左指针向右
} else {
result[index] = right_square; // 否则,将右平方值存入新数组
right--; // 移动右指针向左
}
index--; // 移动新数组的索引位置向前
}
return result; // 返回存储平方结果的新数组
}
int main() {
vector<int> nums = {-4, -1, 0, 3, 10}; // 输入的整数数组
vector<int> result = sortedSquares(nums); // 调用函数得到平方结果
for (int i = 0; i < result.size(); i++) { // 遍历并输出结果
cout << result[i] << " ";
}
return 0; // 返回程序的退出码
}
????????时间复杂度:O(n)
????????空间复杂度:O(n), 其中n为nums数组的长度,且辅助数组的长度为n。
????????懒得布置环境,Acwing的A+B题目永远的神!