一、977.有序数组的平方的链接与题目描述
977. 有序数组的平方的链接如下所示:https://leetcode.cn/problems/squares-of-a-sorted-array/description/https://leetcode.cn/problems/squares-of-a-sorted-array/description/
给你一个按 非递减顺序 排序的整数数组 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] <= 104
nums
已按 非递减顺序 排序
进阶:
- 请你设计时间复杂度为
O(n)
的算法解决本问题
二、977.有序数组的平方的c++代码:
第一种方法:双指针的时间复杂度o(n),具体代码如下:
vector<int> result(nums.size(), 0);int n=nums.size()-1;int left=0, right=n;while(left<=right){if(pow(nums[left], 2)>pow(nums[right], 2)){result[n--]=pow(nums[left], 2);left++;}else{result[n--]=pow(nums[right], 2);right--;}}return result;
第二种方法:快速排序的时间复杂度o(nlogn) ,具体代码如下:
for(int i=0;i<=nums.size()-1;i++){nums[i]*=nums[i]; //快速排序}sort(nums.begin(), nums.end());return nums;
三、解题思路
本题主要讲解双指针的算法思路,下面的本题的4个步骤:
- 定义左指针的索引值为0,右指针为nums.size()-1,容器result装平方后的数组元素;
- 用while判断条件,如果左指针的值小于等于右指针的值,则循环继续,反之,则终止;
- 判断数组开始的值的平方是否大于末尾的值的平方,如果大于,输入result[n--]=pow(nums[left], 2); left++,反之,则result[n--]=pow(nums[right], 2); right--;
- 最后输出result,得出答案。
感谢各位读者的阅读与支持,您的支持是我前进的动力!我希望我的博文能够带给您双指针的一些算法知识和启发。如果您有任何问题或意见,请随时联系我或在评论区评论。希望本题的算法知识对大家有帮助,谢谢各位读者的支持!!!