将数组 nums 中的数平方，然后排序。因为使用了排序算法, 时间和空间复杂度都很高。
class Solution {
public int[] sortedSquares(int[] nums) {
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
ans[i] = nums[i] * nums[i];
}
Arrays.sort(ans);
return ans;
}
}
2.双指针思想
2.1、方法一：
数组原本是有序的, 只是在平方之后就变得无序了, 根本原因就是数组中的负数 平方之后可能成为最大数了, 那么数组元素 平方后的最大值就在数组的两端, 不是最左边就是最右边, 不可能是中间。
要确定数组中元素平方后的最大值的位置。可以用双指针指向数组的两端, 必定能找到平方后的最大值, 将其放到新数组末尾, 之后两个指针不断向中间移动。通过比较两个指针平方后的大小, 就能不断地将当前的最大值放入数组的尾部, 直到两个指针相遇为止。
class Solution {
public int[] sortedSquares(int[] nums) {
int right = nums.length - 1;
int left = 0;
int[] res = new int[nums.length];
int index = res.length - 1;
while (left <= right) {
if (nums[left] * nums[left] > nums[right] * nums[right]) {
res[index--] = nums[left] * nums[left];
++left;
} else {
res[index--] = nums[right] * nums[right];
--right;
}
}
return res;
}
}
2.2、方法二：
另外一种稍微麻烦一点的方式就是 先找到数组中 负值和正值的分界点, 相当于找到了平方后的最小值, 然后向两边不断进行遍历。这种方法多了一层循环来找分界点。
class Solution {
public int[] sortedSquares(int[] nums) {
int n=nums.length;
int negative=-1;
for(int i=0;i=0||j
