2016-06-29 17 views
2

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.

+0

Sie haben die maximale Anzahl der Segmente und Punkte zu sagen, für eine solche Online-Richter wie Frage, sollte vorgesehen werden? – shole

+1

Segmente und Punkte liegen zwischen 1 und 50.000. – Nooblhu

+0

Überschneidet sich das Segment? – shole

Antwort

1

bekommen Dies ist eine Implementierung ähnlich wie @ shole Idee:

public class SegmentsAlgorithm { 

    private PriorityQueue<int[]> remainSegments = new PriorityQueue<>((o0, o1) -> Integer.compare(o0[0], o1[0])); 
    private SegmentWeight[] arraySegments; 

    public void addSegment(int begin, int end) { 
     remainSegments.add(new int[]{begin, end}); 
    } 

    public void prepareArrayCache() { 
     List<SegmentWeight> preCalculate = new ArrayList<>(); 
     PriorityQueue<int[]> currentSegmentsByEnds = new PriorityQueue<>((o0, o1) -> Integer.compare(o0[1], o1[1])); 
     int begin = remainSegments.peek()[0]; 
     while (!remainSegments.isEmpty() && remainSegments.peek()[0] == begin) { 
      currentSegmentsByEnds.add(remainSegments.poll()); 
     } 
     preCalculate.add(new SegmentWeight(begin, currentSegmentsByEnds.size())); 
     int next; 
     while (!remainSegments.isEmpty()) { 
      if (currentSegmentsByEnds.isEmpty()) { 
       next = remainSegments.peek()[0]; 
      } else { 
       next = Math.min(currentSegmentsByEnds.peek()[1], remainSegments.peek()[0]); 
      } 
      while (!currentSegmentsByEnds.isEmpty() && currentSegmentsByEnds.peek()[1] == next) { 
       currentSegmentsByEnds.poll(); 
      } 
      while (!remainSegments.isEmpty() && remainSegments.peek()[0] == next) { 
       currentSegmentsByEnds.add(remainSegments.poll()); 
      } 
      preCalculate.add(new SegmentWeight(next, currentSegmentsByEnds.size())); 
     } 
     while (!currentSegmentsByEnds.isEmpty()) { 
      next = currentSegmentsByEnds.peek()[1]; 
      while (!currentSegmentsByEnds.isEmpty() && currentSegmentsByEnds.peek()[1] == next) { 
       currentSegmentsByEnds.poll(); 
      } 
      preCalculate.add(new SegmentWeight(next, currentSegmentsByEnds.size())); 
     } 
     SegmentWeight[] arraySearch = new SegmentWeight[preCalculate.size()]; 
     int i = 0; 
     for (SegmentWeight l : preCalculate) { 
      arraySearch[i++] = l; 
     } 
     this.arraySegments = arraySearch; 
    } 

    public int searchPoint(int p) { 
     int result = 0; 
     if (arraySegments != null && arraySegments.length > 0 && arraySegments[0].begin <= p) { 
      int index = Arrays.binarySearch(arraySegments, new SegmentWeight(p, 0), (o0, o1) -> Integer.compare(o0.begin, o1.begin)); 
      if (index < 0){ // Bug fixed 
       index = - 2 - index; 
      } 
      if (index >= 0 && index < arraySegments.length) { // Protection added 
       result = arraySegments[index].weight; 
      } 
     } 
     return result; 
    } 

    public static void main(String[] args) { 
     SegmentsAlgorithm algorithm = new SegmentsAlgorithm(); 
     int[][] segments = {{0, 5},{3, 10},{8, 9},{14, 20},{12, 28}}; 
     for (int[] segment : segments) { 
      algorithm.addSegment(segment[0], segment[1]); 
     } 
     algorithm.prepareArrayCache(); 

     int[] points = {-1, 2, 4, 6, 11, 28}; 

     for (int point: points) { 
      System.out.println(point + ": " + algorithm.searchPoint(point)); 
     } 
    } 

    public static class SegmentWeight { 

     int begin; 
     int weight; 

     public SegmentWeight(int begin, int weight) { 
      this.begin = begin; 
      this.weight = weight; 
     } 
    } 
} 

Er druckt:

-1: 0 
2: 1 
4: 2 
6: 1 
11: 2 
28: 0 

EDITED:

public static void main(String[] args) { 
    SegmentsAlgorithm algorithm = new SegmentsAlgorithm(); 
    Scanner scanner = new Scanner(System.in); 
    int n = scanner.nextInt(); 
    int m = scanner.nextInt(); 
    for (int i = 0; i < n; i++) { 
     algorithm.addSegment(scanner.nextInt(), scanner.nextInt()); 
    } 
    algorithm.prepareArrayCache(); 
    for (int i = 0; i < m; i++) { 
     System.out.print(algorithm.searchPoint(scanner.nextInt())+ " "); 
    } 
    System.out.println(); 
} 
+0

Ihre Codes funktioniert gut, aber Ich muss es mit Testfällen beweisen. Wie würdest du die 2D-Array-Segmente [] [] so anpassen, dass die Eingabe vom Scanner wie folgt erfolgt: {{1., 2.}, {3., 4.}, {5., 6.} ......? – Nooblhu

+0

@Nooblhu Bearbeitet, Es ist für Scanner angepasst. –

+0

Nicht sicher warum, wirft ArrayIndexOutofBounds bei searchPoint Methode: Ergebnis = ArraySegmente [Math.abs (Index)]. Gewicht; wenn in System.out.print aufgerufen (algorithm.searchPoint (scanner.nextInt()) + ""); (mit Testfall der Frage) – Nooblhu

2

die Constraints von OP Gegeben sei n die Anzahl der Segmente, m die Anzahl der Punkte sein Abfrage zu sein, wo n,m < = 5 * 10^4, ich mit einer O(nlg(n) + mlg(n)) Lösung kommen kann (was sein sollte genug, um die meisten Online-Richter passieren)

Da jede Abfrage eine Überprüfung Problem ist: kann der Punkt von einigen Intervallen abgedeckt werden, ja oder nein, wir brauchen nicht zu finden, was/wie viele Intervalle der Punkt hat wurde abgedeckt.

Umriss des Algorithmus:

  1. sortieren alle Intervalle ersten Punkt beginnen, wenn tie dann durch Länge (ganz rechts Punkt enden)
  2. Versuchen Sie, die Intervalle zu verschmelzen einige disjoint überlappende Intervalle zu erhalten. Für z.B. (0,5), (2,9), (3,7), (3,5), (12,15) erhalten Sie (0,9), (12,15). Da die Intervalle sortiert sind, kann dies gierig in O(n)
  3. durchgeführt werden. Oben sind die Vorberechnung, jetzt für jeden Punkt, die wir mit den disjunkten Intervallen abfragen.Einfach binäre Suche, wenn eine Intervall solchen Punkt enthält, jede Abfrage O(lg(n)) ist und wir haben m Punkte, so total O(m lg(n))

ganzen Algorithmus kombiniert, werden wir einen O(nlg(n) + mlg(n)) Algorithmus

+0

Wenn Segmente in 2. zusammengeführt werden und sich überlappen, wie kann ich zählen, wie viele Segmente das tut Punkt schneidet sich? Soll ich die Punkte auch in 2. zusammenführen? Ich gehe davon aus, dass ich in 3 mit binärer Suche nach Punkten suche. Ich bin mir nicht sicher, ob mein Java-Level hoch genug ist, um diese 3 Punkte in Code zu konvertieren, aber ich habe einen Startpunkt – Nooblhu

+0

Nein, du mischt es. Diese Methode funktioniert, vorausgesetzt, Sie müssen NICHT wissen, wie viele Segmente der Punkt schneidet, sondern nur "JA" oder "NEIN". Und in 2, das ist die Vorbereitung für 3, werden keine Punkte berücksichtigt, Sie versuchen nur, die Eingabedaten in eine günstigere Form zu bringen (disjunkte und sortierte Intervalle). Dann beginnen Sie, den Punkt nacheinander zu suchen, indem Sie diese transformierten Daten verwenden . Ja in Punkt 3 für jeden Punkt verwenden wir binäre Suche wie ich sagte, Sie können lower_bound() oder upper_bound() in C++ lesen (nicht sicher, ob Java ähnliche integrierte Funktionen) – shole

+0

Sorry, ich glaube, ich wählte ein Eingabe- und Ausgabe Beispiel das gab nicht an, dass ich zählen musste, wenn der Punkt in mehr als einem Segment erscheint. Ich habe gerade dieses Detail geändert. – Nooblhu