977. 有序数组的平方 #
Difficulty: 简单
给定一个按非递减顺序排序的整数数组 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] <= 10000A已按非递减顺序排序。
题解 #
题解一：直接排序 #
class Solution {
public int[] sortedSquares(int[] nums) {
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
result[i] = nums[i] * nums[i];
}
Arrays.sort(result);
return result;
}
}
复杂度分析 #
-
时间复杂度：O(nlogn)，其中 n 是数组 A 的长度。
-
空间复杂度：O(logn)。
解法二：双指针解法 #
class Solution {
public int[] sortedSquares(int[] A) {
int n = A.length;
int negative = -1;
for (int i = 0; i < n; ++i) {
if (A[i] < 0) {
negative = i;
} else {
break;
}
}
int[] ans = new int[n];
int index = 0, i = negative, j = negative + 1;
while (i >= 0 || j < n) {
if (i < 0) {
ans[index] = A[j] * A[j];
++j;
} else if (j == n) {
ans[index] = A[i] * A[i];
--i;
} else if (A[i] * A[i] < A[j] * A[j]) {
ans[index] = A[i] * A[i];
--i;
} else {
ans[index] = A[j] * A[j];
++j;
}
++index;
}
return ans;
}
}
复杂度分析 #
-
时间复杂度：O(n)，其中 n 是数组 A 的长度。
-
空间复杂度：O(1)。
题解三：双指针解法 #
class Solution {
public int[] sortedSquares(int[] A) {
int[] result = new int[A.length];
for (int i = 0, j = A.length - 1, pos = A.length - 1; i <= j; pos--) {
if (A[i] * A[i] > A[j] * A[j]) {
result[pos] = A[i] * A[i];
i++;
} else {
result[pos] = A[j] * A[j];
j--;
}
}
return result;
}
}
复杂度分析 #
-
时间复杂度：O(n)，其中 n 是数组 A 的长度。
-
空间复杂度：O(1)。