Skip to content

Instantly share code, notes, and snippets.

@maksverver
Last active April 2, 2024 17:58
Show Gist options
  • Save maksverver/5abf52c8e4ba79857fa2646ea091bf60 to your computer and use it in GitHub Desktop.
Save maksverver/5abf52c8e4ba79857fa2646ea091bf60 to your computer and use it in GitHub Desktop.
import java.util.*;
import java.util.stream.Collectors;
import com.google.common.collect.SortedMultiset;
import com.google.common.collect.TreeMultiset;
class Test {
static List<Integer> solvePriorityQueue(List<Integer> list, int m) {
PriorityQueue<Integer> pq = new PriorityQueue<>(list.subList(0, m));
List<Integer> res = new ArrayList<>(list.size() - m + 1);
Integer mth = pq.peek();
res.add(mth);
for (int i : list.subList(m, list.size())) {
if (i > mth) {
pq.add(i);
pq.poll();
mth = pq.peek();
}
res.add(mth);
}
return res;
}
static List<Integer> solveSortedMultiset(List<Integer> list, int m) {
List<Integer> result = new ArrayList<>(list.size() - m + 1);
SortedMultiset<Integer> largest = list.subList(0, m).stream()
.collect(Collectors.toCollection(TreeMultiset::create));
result.add(largest.firstEntry().getElement());
for (Integer element : list.subList(m, list.size())) {
Integer firstElement = largest.firstEntry().getElement();
if (element <= firstElement) {
result.add(firstElement);
} else {
largest.remove(firstElement);
largest.add(element);
result.add(largest.firstEntry().getElement());
}
}
return result;
}
public static void main(String... args) {
int n = 1000000;
int m = 50000;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; ++i)
list.add(i + 1);
Collections.shuffle(list);
List<Integer> a = solvePriorityQueue(list, m);
List<Integer> b = solveSortedMultiset(list, m);
if (!a.equals(b))
throw new RuntimeException();
for (int repeats = 0; repeats < 10; ++repeats) {
long start = System.currentTimeMillis();
List<Integer> c = solvePriorityQueue(list, m);
long elapsed = System.currentTimeMillis() - start;
System.out.println("solvePriorityQueue() " + elapsed + " ms");
if (!c.equals(a))
throw new RuntimeException();
}
for (int repeats = 0; repeats < 10; ++repeats) {
long start = System.currentTimeMillis();
List<Integer> c = solveSortedMultiset(list, m);
long elapsed = System.currentTimeMillis() - start;
System.out.println("solveSortedMultiset() " + elapsed + " ms");
if (!c.equals(a))
throw new RuntimeException();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment