-
Notifications
You must be signed in to change notification settings - Fork 14
/
SortedSquares.java
68 lines (59 loc) · 2.2 KB
/
SortedSquares.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package by.andd3dfx.common;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;
/**
* <pre>
* <a href="https://leetcode.com/problems/squares-of-a-sorted-array/">Task description</a>
*
* Дан массив целых чисел, отсортированный по возрастанию.
* Вернуть массив, содержащий эл-ты исходного массива в квадрате, также отсортированный по возрастанию.
*
* Пример:
* [-5,-3,0,1,2,4] -> [0,1,4,9,16,25]
* </pre>
*
* @see <a href="https://youtu.be/49DpyzZN4NM">Video solution</a>
*/
public class SortedSquares {
public static Integer[] transformUsingSorting(Integer[] items) {
return Arrays.stream(items)
.map(integer -> integer * integer)
.sorted()
.collect(Collectors.toList())
.toArray(new Integer[0]);
}
public static Integer[] transformUsingDeque(Integer[] items) {
int left = 0;
int right = items.length - 1;
Deque<Integer> queue = new ArrayDeque<>();
while (left <= right) {
var leftValue = items[left] * items[left];
var rightValue = items[right] * items[right];
if (leftValue < rightValue) {
queue.addFirst(rightValue);
right--;
} else {
queue.addFirst(leftValue);
left++;
}
}
return queue.toArray(new Integer[0]);
}
public static Integer[] transformUsingPriorityQueue(Integer[] items) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(value -> value));
for (var item : items) {
priorityQueue.add(item * item);
}
List<Integer> result = new ArrayList<>();
while (!priorityQueue.isEmpty()) {
result.add(priorityQueue.poll());
}
return result.toArray(new Integer[0]);
}
}