Ich habe 2 Integrale gegeben, die erste ist die Anzahl der Segmente (Xi, Xj) und die zweite ist die Anzahl der Punkte, die können oder können in diesen Segmenten sein.Wie kann ich diesen Algorithmus verbessern, um die Laufzeit zu optimieren (finde Punkte in Segmenten)
Als Beispiel könnte der Eingang sein:
2 3
0 5
8 10
1 6 11
Wo, in erster Linie, 2 bedeutet "2 Segmente" und 3 bedeutet "3 Punkte". Die 2 Segmente sind "0 bis 5" und "8 bis 10", und die Punkte zu suchen sind 1, 6, 11. Der Ausgang
1 0 0
Wo Punkt 1 in Segment „0 bis 5 ", und Punkt 6 und 11 sind in keinem Segment. Wenn ein Punkt in mehr als ein Segment angezeigt wird, wie ein 3 würde der Ausgang 2 seine
Der ursprüngliche Code, war nur eine Doppelschleife, die Punkte zwischen den Segmenten zu suchen. Ich benutzte den Java Arrays Quicksort (so modifiziert, wenn er Endpunkte von Segmenten sortiert, sortiert auch Startpunkte, also beginnen [i] und Ende [i] zum selben Segment i), um die Geschwindigkeit der Doppelschleife zu verbessern, aber es ist nicht genug.
Der nächste Code funktioniert gut, aber wenn zu viele Segmente gibt es wird es sehr langsam:
public class PointsAndSegments {
private static int[] fastCountSegments(int[] starts, int[] ends, int[] points) {
sort(starts, ends);
int[] cnt2 = CountSegments(starts,ends,points);
return cnt2;
}
private static void dualPivotQuicksort(int[] a, int[] b, int left,int right, int div) {
int len = right - left;
if (len < 27) { // insertion sort for tiny array
for (int i = left + 1; i <= right; i++) {
for (int j = i; j > left && b[j] < b[j - 1]; j--) {
swap(a, b, j, j - 1);
}
}
return;
}
int third = len/div;
// "medians"
int m1 = left + third;
int m2 = right - third;
if (m1 <= left) {
m1 = left + 1;
}
if (m2 >= right) {
m2 = right - 1;
}
if (a[m1] < a[m2]) {
swap(a, b, m1, left);
swap(a, b, m2, right);
}
else {
swap(a, b, m1, right);
swap(a, b, m2, left);
}
// pivots
int pivot1 = b[left];
int pivot2 = b[right];
// pointers
int less = left + 1;
int great = right - 1;
// sorting
for (int k = less; k <= great; k++) {
if (b[k] < pivot1) {
swap(a, b, k, less++);
}
else if (b[k] > pivot2) {
while (k < great && b[great] > pivot2) {
great--;
}
swap(a, b, k, great--);
if (b[k] < pivot1) {
swap(a, b, k, less++);
}
}
}
// swaps
int dist = great - less;
if (dist < 13) {
div++;
}
swap(a, b, less - 1, left);
swap(a, b, great + 1, right);
// subarrays
dualPivotQuicksort(a, b, left, less - 2, div);
dualPivotQuicksort(a, b, great + 2, right, div);
// equal elements
if (dist > len - 13 && pivot1 != pivot2) {
for (int k = less; k <= great; k++) {
if (b[k] == pivot1) {
swap(a, b, k, less++);
}
else if (b[k] == pivot2) {
swap(a, b, k, great--);
if (b[k] == pivot1) {
swap(a, b, k, less++);
}
}
}
}
// subarray
if (pivot1 < pivot2) {
dualPivotQuicksort(a, b, less, great, div);
}
}
public static void sort(int[] a, int[] b) {
sort(a, b, 0, b.length);
}
public static void sort(int[] a, int[] b, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
dualPivotQuicksort(a, b, fromIndex, toIndex - 1, 3);
}
private static void rangeCheck(int length, int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IllegalArgumentException("fromIndex > toIndex");
}
if (fromIndex < 0) {
throw new ArrayIndexOutOfBoundsException(fromIndex);
}
if (toIndex > length) {
throw new ArrayIndexOutOfBoundsException(toIndex);
}
}
private static void swap(int[] a, int[] b, int i, int j) {
int swap1 = a[i];
int swap2 = b[i];
a[i] = a[j];
b[i] = b[j];
a[j] = swap1;
b[j] = swap2;
}
private static int[] naiveCountSegments(int[] starts, int[] ends, int[] points) {
int[] cnt = new int[points.length];
for (int i = 0; i < points.length; i++) {
for (int j = 0; j < starts.length; j++) {
if (starts[j] <= points[i] && points[i] <= ends[j]) {
cnt[i]++;
}
}
}
return cnt;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n, m;
n = scanner.nextInt();
m = scanner.nextInt();
int[] starts = new int[n];
int[] ends = new int[n];
int[] points = new int[m];
for (int i = 0; i < n; i++) {
starts[i] = scanner.nextInt();
ends[i] = scanner.nextInt();
}
for (int i = 0; i < m; i++) {
points[i] = scanner.nextInt();
}
//use fastCountSegments
int[] cnt = fastCountSegments(starts, ends, points);
for (int x : cnt) {
System.out.print(x + " ");
}
}
Ich glaube, das Problem in dem CountSegments ist() -Methode, aber ich bin eine andere Art und Weise nicht sicher, ob es zu lösen . Angeblich sollte ich einen Divide and Conquer-Algorithmus verwenden, aber nach 4 Tagen bin ich bereit für jede Lösung. Ich fand a similar problem in CodeForces, aber die Ausgabe ist anders und die meisten Lösungen sind in C++. Da ich erst seit 3 Monaten Java lerne, glaube ich, dass ich mein Wissenslimit erreicht habe.
Sie haben die maximale Anzahl der Segmente und Punkte zu sagen, für eine solche Online-Richter wie Frage, sollte vorgesehen werden? – shole
Segmente und Punkte liegen zwischen 1 und 50.000. – Nooblhu
Überschneidet sich das Segment? – shole