内容简介：题目描述：给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。示例 1：
题目描述：
给定一个按非递减顺序 排序 的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
示例 1：
输入：[-4,-1,0,3,10] 输出：[0,1,9,16,100]
示例 2：
输入：[-7,-3,2,3,11] 输出：[4,9,9,49,121]
提示：
- 1<= A.length <= 10000
- -10000 <= A[i] <= 10000
- A 已按非递减顺序排序。
解决方案
方法一：排序
思路与算法
创建一个新的数组，它每个元素是给定数组对应位置元素的平方，然后排序这个数组。
public int[] sortedSquares(int[] A) {
int[] B = new int[A.length];
for (int i=0; i < A.length; i++) {
B[i] = (A[i]) * (A[i]);
}
Arrays.sort(B);
return B;
}
复杂度分析
-
时间复杂度：O(N \log N)O(NlogN)，其中 NN 是数组 A 的长度。
-
空间复杂度：O(N)O(N)。
方法二：双指针
思路
因为数组 A 已经排好序了， 所以可以说数组中的负数已经按照平方值降序排好了，数组中的非负数已经按照平方值升序排好了。
举一个例子，若给定数组为 [-3, -2, -1, 4, 5, 6]，数组中负数部分 [-3, -2, -1] 的平方为 [9, 4, 1]，数组中非负部分 [4, 5, 6] 的平方为 [16, 25, 36]。我们的策略就是从前向后遍历数组中的非负数部分，并且反向遍历数组中的负数部分。
算法
我们可以使用两个指针分别读取数组的非负部分与负数部分 —— 指针 i 反向读取负数部分，指针 j 正向读取非负数部分。
那么，现在我们就在使用两个指针分别读取两个递增的数组了（按元素的平方排序）。接下来，我们可以使用双指针的技巧合并这两个数组。
public int[] sortedSquares(int[] A) {
int N = A.length;
int j = 0;
while (j < N && A[j] < 0)
j++;
int i = j-1;
int[] ans = new int[N];
int t = 0;
while (i >= 0 && j < N) {
if (A[i] * A[i] < A[j] * A[j]) {
ans[t++] = A[i] * A[i];
i--;
} else {
ans[t++] = A[j] * A[j];
j++;
}
}
while (i >= 0) {
ans[t++] = A[i] * A[i];
i--;
}
while (j < N) {
ans[t++] = A[j] * A[j];
j++;
}
return ans;
}
以上所述就是小编给大家介绍的《LeetCode 每日一题（day 1）》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
黑客简史：棱镜中的帝国
刘创 / 电子工业出版社 / 2015-1 / 39.80元
“黑客”，伴随着计算机和互联网而诞生，他们掌握着前沿的计算机和网络技术，能够发现并利用计算机系统和网络的弱点，他们的行为动机多样，因此我们必须对这一群体进行分解，认识他们及其技术的两面性——“黑客”中那些不断拓展技术边界、富于创造力的，和那些掌握技术、却利欲熏心的，就像硬币的两面，谁都无法清晰地辨别是非。相对于主流文化，黑客的行为方式和理念等形成了一种“亚文化”，与主流文化相互作用。一起来看看 《黑客简史：棱镜中的帝国》 这本书的介绍吧!
