这是悦乐书的第369次更新，第397篇原创
01看题和准备
今天介绍的是LeetCode算法题中Easy级别的第231题（顺位题号是977）。给定一个整数数组A按有序递增顺序排序，返回每个数字的平方，也按有序递增顺序返回。例如：
输入：[ - 4，-1,0,3,10]
输出：[0,1,9,16,100]
输入：[ - 7，-3,2,3,11]
输出：[4,9,9,49,121]
注意：
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A按有序递增顺序排序。
02 第一种解法
直接翻译题目即可，借助Arrays的sort方法来对结果数组排序。
此解法的时间复杂度是O(N log(N))，空间复杂度是O(N)。
public int[] sortedSquares(int[] A) {
int n = A.length, i = 0;
int[] result = new int[n];
for (int num : A) {
result[i++] = num*num;
}
Arrays.sort(result);
return result;
}
03 第二种解法
不使用新数组来作为结果数组返回，将A中的负数变正数，再排序，再取平方。
此解法的时间复杂度是O(N log(N))，空间复杂度是O(1)。
public int[] sortedSquares2(int[] A) {
int n = A.length;
for (int i=0; i<n; i++) {
A[i] = A[i]<0 ? -A[i] : A[i];
}
Arrays.sort(A);
for (int j=0; j<n; j++) {
A[j] = A[j]*A[j];
}
return A;
}
04 第三种解法
使用计数排序，对A中的数进行处理，然后计算平方。
此解法的时间复杂度是O(N)，空间复杂度是O(N)。
public int[] sortedSquares3(int[] A) {
int n = A.length, index = 0;
int[] sort = new int[10001];
int len = sort.length;
for (int i=0; i<len; i++) {
sort[i] = 1;
}
for (int num : A) {
sort[num<0 ? -num : num]++;
}
int[] result = new int[n];
for (int j=0; j<sort.length; j++) {
if (sort[j] > 1) {
while (sort[j]-1 > 1) {
result[index++] = j*j;
sort[j]--;
}
result[index++] = j*j;
}
}
return result;
}
05 第四种解法
双指针，前后比较两个数，如果前面的数的绝对值大于后面的数，那么结果数组中当前位元素为前面的元素平方，反之就是后面的元素平方为结果数组当前位元素。
此解法的时间复杂度是O(N)，空间复杂度是O(N)。
public int[] sortedSquares4(int[] A) {
int n = A.length;
int start = 0, end = n-1;
int[] result = new int[n];
for (int i=n-1; i>=0; i--) {
if (Math.abs(A[start]) > Math.abs(A[end])) {
result[i] = A[start]*A[start];
start++;
} else {
result[i] = A[end]*A[end];
end--;
}
}
return result;
}
06 小结
算法专题目前已连续日更超过七个月，算法题文章237+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
