政府 门户 网站建设谷歌浏览器官网下载安装

有序数组的平方

本节对应代码随想录中：代码随想录，讲解视频：有序数组的平方_哔哩哔哩_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:vector<int> sortedSquares(vector<int>& A) {for (int i = 0; i < A.size(); i++) {A[i] *= A[i];}sort(A.begin(), A.end()); // 快速排序return A;}
};

双指针

首先来说一下为什么可以使用双指针

元素本来就是有序的，只不过因为里面有负数，负数平方后就可能大于某些正数的平方，从而顺序会发生变化

但是无论正数还是负数，其绝对值越大，那么它平方后也就会越大，即数组越靠近两边，平方后就会越大

那么我们就可以使用双指针，一个指向最左边，一个指向最右边。比较两边哪个平方后更大，存入新的数组中。然后更新指针，直到两个指针相遇，说明遍历完了所有的元素。

我的解法如下：

class Solution {public:vector<int> sortedSquares(vector<int>& nums) {int n = nums.size(), j = n - 1, k = n - 1;vector<int> 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;}
};

看了别人的解法有几点可以注意下

• vector<int> copy = nums; 也可以写成 vector<int> copy(nums.size(), 0);，区别是前者会复制 nums 的元素，而后者会将所有元素置0
• for 循环中的 i<n 可以 i <= j;，这样就不用再用 if 判断相等时 break 了
• for 循环中的 i++,k-- 可以在 for 循环里面写，其实这样更符合逻辑，因为并不是每次都要 i++,k-- ，只有满足特定情况时才会这样
• 不一定要用 for 循环，用 while(i<=j) 来循环更符合逻辑

双指针思考：上一小节的移除元素中，两个指针都在最左边开始，只不过一个快点，一个慢点，快的用来遍历一遍元素，慢的用来指向满足条件的新的数组的下标；而这一节的双指针，一个在左边，一个在右边，两个指针不断比较，然后都往中间靠拢。上一小节的终止条件是快的指针遍历完一遍就停，而这一节的是当两个指针相遇时(i <= j;)停止