常州个人网站设计,女教师遭网课入侵直播录屏曝光i,网络公司经营范围大全,餐饮企业网站建设977. 有序数组的平方
题目#xff1a;
给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 排序。
示例#xff1a;
示例 1#xff1a;
输入#xff1a;nums [-4,-1,0,3,10]
输出#xff1a;[…977. 有序数组的平方
题目
给你一个按 非递减顺序 排序的整数数组 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]提示
1 nums.length 104-104 nums[i] 104nums 已按 非递减顺序 排序
进阶
请你设计时间复杂度为 O(n) 的算法解决本问题
解题
方法一直接排序
最简单的方法就是将数组 nums 中的数平方后直接排序。
class Solution {
public:vectorint sortedSquares(vectorint nums) {vectorint ans;for(int num : nums) {ans.push_back(num * num);}sort(ans.begin(),ans.end());return ans;}
};复杂度分析
时间复杂度O(nlogn)其中 n 是数组 nums 的长度。
空间复杂度O(logn)。除了存储答案的数组以外我们需要 O(logn) 的栈空间进行排序。
方法二双指针法
方法一没有利用「数组 nums 已经按照升序排序」这个条件。显然如果数组 nums 中的所有数都是非负数那么将每个数平方后数组仍然保持升序如果数组 nums 中的所有数都是负数那么将每个数平方后数组会保持降序。
这样一来如果我们能够找到数组 nums 中负数与非负数的分界线那么就可以用类似「归并排序」的方法了。具体地我们设 neg 为数组 nums 中负数与非负数的分界线也就是说nums[0] 到 nums[neg] 均为负数而 nums[neg1] 到 nums[n−1] 均为非负数。当我们将数组 nums 中的数平方后那么 nums[0] 到 nums[neg] 单调递减nums[neg1] 到 nums[n−1] 单调递增。
由于我们得到了两个已经有序的子数组因此就可以使用归并的方法进行排序了。具体地使用两个指针分别指向位置 neg 和 neg1每次比较两个指针对应的数选择较小的那个放入答案并移动指针。当某一指针移至边界时将另一指针还未遍历到的数依次放入答案。
class Solution {
public:vectorint sortedSquares(vectorint nums) {int n nums.size();int negative -1;for(int i 0; i n; i) {if(nums[i] 0) {negative i;} else {break;}}vectorint ans;int i negative, j negative 1;while(i 0 || j n) {if(i 0) { // 说明数组没有负数ans.push_back(nums[j]*nums[j]);j;} else if (j n) { // 说明数组全是负数ans.push_back(nums[i]*nums[i]);--i;} else if(nums[i]*nums[i] nums[j]*nums[j]) { // 数组有正有负比较两边ans.push_back(nums[i]*nums[i]);--i;} else {ans.push_back(nums[j]*nums[j]);j;}}return ans;}
};复杂度分析 时间复杂度O(n)其中 n 是数组 nums 的长度。 空间复杂度O(1)。除了存储答案的数组以外我们只需要维护常量空间。
方法三双指针
同样地我们可以使用两个指针分别指向位置 0 和 n−1每次比较两个指针对应的数选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况读者可以仔细思考其精髓所在。
因此对于前半部分负数而言从前往后遍历平方后相当于逆序从大到小对于后半部分正数而言从后往前遍历也相当于逆序从大到小因此可以看成两个逆序数组数组从大到小排序然后取较大者插入到答案数组尾部中。
class Solution {
public:vectorint sortedSquares(vectorint nums) {int n nums.size();vectorint ans(n);for (int i 0, j n - 1, pos n - 1; i j;) {if (nums[i] * nums[i] nums[j] * nums[j]) {ans[pos] nums[i] * nums[i];i;}else {ans[pos] nums[j] * nums[j];--j;}--pos;}return ans;}
};复杂度分析 时间复杂度O(n)其中 n 是数组 nums 的长度。 空间复杂度O(1)。除了存储答案的数组以外我们只需要维护常量空间。
