【双指针问题】977. 有序数组的平方

Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

🌈个人主页：主页链接

🌈算法专栏：专栏链接

     我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

记录下今天的Leetcode，虽然是一道简单题，但用了两种解法，都挺快的。

目录

题目:

白话讲解:

题解:

解法1:

代码实现:

解法2:

代码实现:

完结撒花：

---

题目:

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

白话讲解:

就是有一个升序的数组,返回每个元素平方组成的新数组,该数组也满足升序的概念.

题解:

分析题目强调的升序数组,我们可以得出每个元素平方后有三种情况

第一种:数组中全为负数,那么在平方后他呈递减的趋势

第二种:数组中全为正数,那么在平方后他呈递增趋势

第三种:数组中既有正数也有负数,那么在平方后他呈二次函数x^2的形式 

解法1:

可以看出,我们需要做的就是找到绝对值最小的元素 然后往两边扩散开(双指针),例如第一种我们找到绝对值最小的元素0,然后往左右两边去扩散开,因为右边没有元素,所以我们将左边元素平方后填入.

再比如第三种:

找到绝对值最小的元素0,之后对两边进行比较

若左边的平方大于右边的平方,则将右边的平方放入答案数组 之后右边的指针向后移动一位.再进行比较,如此循环

当左边到达边界或右边到达边界时退出.再进行一个判断若左边还未到达边界则将左边的元素全部填入答案数组中,反之.(相当于归并排序排序的过程)

代码实现:

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int n=nums.size(),flag=0;for(int i=0;i<n;i++){if(nums[i]<0)flag=i;else break;}int i=flag,j=i+1;vector<int>ans;while(i>=0&&j<n){if(abs(nums[j])<=abs(nums[i]))ans.push_back(nums[j]*nums[j++]);else ans.push_back(nums[i]*nums[i--]);}while(i>=0){ans.push_back(nums[i]*nums[i]);i--;}while(j<n){ans.push_back(nums[j]*nums[j]);j++;}return ans;}
};

 

解法2:

这个解法将三种情况用一种模式来搞定,我们可以发现,

若有 两个指针指向这个数组的首位端,那么平方后一定有,大的一定就是填入数组中的那个,所以我们直接将大的那个数填入答案数组中,即可

代码实现:

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int n=nums.size();vector<int>ans(n);int i=0,j=n-1,cur=n-1;while(i<=j){if(nums[i]*nums[i]<=nums[j]*nums[j]){ans[cur]=nums[j]*nums[j];j--;}else {ans[cur]=nums[i]*nums[i];i++;}cur--;}return ans;}
};

 

完结撒花：

🌈本篇博客的内容【双指针问题 977. 有序数组的平方】已经结束。

        最近在复习要命的线代和计组,只能保证每天一题的频率了(惨兮兮 

🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。

🌈诸君，山顶见！