05 August 2008
一个整数数组按非降序排列，有负数，返回一个数组是每个元素的平方数，也按非降序排列
左右双指针，时间复杂度O(n)，空间O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int[] sortedSquares(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int len = nums.length;
int left = 0;
int right = len - 1;
int[] result = new int[len];
int index = 0;
for (int i = len - 1; i >= 0; i--) { // 左右两端从大的开始前放，如果从小的开始可能会漏掉中间最小的值
if (Math.abs(nums[left]) >= Math.abs(nums[right])) {
result[i] = nums[left] * nums[left];
left++;
} else {
result[i] = nums[right] * nums[right];
right--;
}
}
return result;
}
}
优先队列，时间复杂度O(n)，空间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int[] sortedSquares(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int len = nums.length;
PriorityQueue<Integer> pq = new PriorityQueue<>(len); // min heap
int[] result = new int[len];
for (int num : nums) {
pq.offer(num * num);
}
for (int i = 0; i < len; i++) {
result[i] = pq.poll();
}
return result;
}
}