厦门市建设管理协会网站首页,如何制作论坛网站,做企业网站 需要那些功能,vps 同时做ssh和做网站文章目录有序数组的平方习题暴力排序双指针有序数组的平方
本节对应代码随想录中#xff1a;代码随想录#xff0c;讲解视频#xff1a;有序数组的平方_哔哩哔哩_bilibili
习题
题目链接#xff1a;977. 有序数组的平方 - 力扣#xff08;LeetCode#xff09;
给你一…
文章目录有序数组的平方习题暴力排序双指针有序数组的平方
本节对应代码随想录中代码随想录讲解视频有序数组的平方_哔哩哔哩_bilibili
习题
题目链接977. 有序数组的平方 - 力扣LeetCode
给你一个按非递减顺序排序的整数数组 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]
暴力排序
直接能想到的就是先把每个元素平方然后再进行排序即可
class Solution {
public:vectorint sortedSquares(vectorint A) {for (int i 0; i A.size(); i) {A[i] * A[i];}sort(A.begin(), A.end()); // 快速排序return A;}
};双指针
首先来说一下为什么可以使用双指针
元素本来就是有序的只不过因为里面有负数负数平方后就可能大于某些正数的平方从而顺序会发生变化
但是无论正数还是负数其绝对值越大那么它平方后也就会越大即数组越靠近两边平方后就会越大
那么我们就可以使用双指针一个指向最左边一个指向最右边。比较两边哪个平方后更大存入新的数组中。然后更新指针直到两个指针相遇说明遍历完了所有的元素。
我的解法如下
class Solution {public:vectorint sortedSquares(vectorint nums) {int n nums.size(), j n - 1, k n - 1;vectorint copy nums;for (int i 0; i n; i,k--) {if (i j) {nums[0] copy[i] * copy[i];break;}if (copy[i] * copy[i] copy[j] * copy[j]) {nums[k] copy[i] * copy[i];} else {nums[k] copy[j] * copy[j];j--;i--;} }return nums;}
};看了别人的解法有几点可以注意下
vectorint copy nums; 也可以写成 vectorint copy(nums.size(), 0);区别是前者会复制 nums 的元素而后者会将所有元素置0for 循环中的 in 可以 i j;这样就不用再用 if 判断相等时 break 了for 循环中的 i,k-- 可以在 for 循环里面写其实这样更符合逻辑因为并不是每次都要 i,k-- 只有满足特定情况时才会这样不一定要用 for 循环用 while(ij) 来循环更符合逻辑
双指针思考上一小节的移除元素中两个指针都在最左边开始只不过一个快点一个慢点快的用来遍历一遍元素慢的用来指向满足条件的新的数组的下标而这一节的双指针一个在左边一个在右边两个指针不断比较然后都往中间靠拢。上一小节的终止条件是快的指针遍历完一遍就停而这一节的是当两个指针相遇时(i j;)停止
