So sortieren Sie ein Array von Segmenten (int links, int rechts) in aufsteigender Reihenfolge, aber wenn links (i) = links (i + 1) sortieren Sie es nach rechts (i) und rechts (i + 1)

Question

I haben eine Klasse Segment und ein Array von Segmenten wie folgt aus:

private static class Segment { 
     int number, type; 
     Segment(int number, int type) { 
      this.number = number; 
      this.type = type; 
     } 
} 

Segment[] points = new Segment[n]; 
points={(0,-1),(1,0),(5,1),(6,0),(6,-1),(10,1),(11,0)} 

Element nach links eine Liste von Punkten ist, und die Liste der rechten Seite ist die Art von Punkt: -1 ein Segment, 1 öffnet und schließt Ein Segment und 0 schneidet das Segment. Wie Sie sehen können, ist diese Anordnung bereits nach Nummer sortiert, mit diesem Code (seine eine angepasste SelectionSort):

MAXI den Index der größten "number" Element

private static int maxI(Segment[] segments, int size){ 
    int max=0; 
    for (int i=0; i< size;i++){ 
     if(segments[i].number > segments[max].number){ 
      max=i; 
     } 
    } 
    return max; 
} 

// findet Swap Verfahren tauscht Elemente der Anordnung zwischen index1 und index2

private static void swap(Segment[] segments, int index1, int index2){ 
      int temp1; 
      int temp2; 
      temp1 = segments[index1].number; 
      temp2 = segments[index1].type; 
      segments[index1].number=segments[index2].number; 
      segments[index1].type=segments[index2].type; 
      segments[index2].number=temp1; 
      segments[index2].type=temp2; 
    } 

SelectSort ist das Sortierverfahren (da Arrays.sort gewohnt mit „Segmente“ arbeiten)

0.123.

war der ursprüngliche Eingang 2 Bereiche und 3 Schnittpunkte:

Range 1: 0 5 
Range 2: 6 10 
Intersection points: 1 6 11 

das Ergebnis wie oben So nach dem Sortieren ist:

(0,-1),(1,0),(5,1),(6,0),(6,-1),(10,1),(11,0) 

ich die MAXI-Methode zu ändern habe versucht, so 6, -1 kommt vor 6,0 (-1 < 0) eine zweite if-Anweisung verwendet:

if (segments[i].number = segments[max].number && segments[i].type > segments[max].type) 

Aber es m Esse die Ausgabe. Da die Eingabe zufällig ist, muss der Code darauf vorbereitet sein, Testfälle zu sortieren, in denen viele Zahlen gleich sind.

Die nächste Frage, die ich mit diesem Thema gesehen habe, ist one made in C++, Ich lerne gerade Java, also habe ich genug zu kämpfen, um zu versuchen, C++ zu verstehen. Ich fühle, dass die Antwort nah ist, aber nicht sicher, was ich vermisse. Vielleicht verwende ich die falsche Datenstruktur. Danach durchquere ich einfach das Array und addiere die Summe der Typen. Wenn also eine Zahl die 3 Öffnung der Bereiche (x, -1) passiert, ist es -3, in Absolut = 3 also schneidet es 3 Bereiche, was die Antwort ist Ich werde brauchen.

Answer 1

Erstellen Sie einfach eine Comparator, die number dann type vergleicht, dann können Sie Arrays.sort() verwenden. Wenn Sie Java 8 haben, können Sie es wie folgt tun:

Arrays.sort(points, Comparator.comparingInt((Segment s) -> s.number).thenComparingInt((Segment s) -> s.type)); 

Wenn Sie mit Java 7, können Sie dies tun:

Arrays.sort(points, new Comparator<Segment>() { 
    @Override 
    public int compare(Segment s1, Segment s2) { 
     int result = Integer.compare(s1.number, s2.number); 
     if (result == 0) { 
      result = Integer.compare(s1.type, s2.type); 
     } 
     return result; 
    } 
}); 

Alternativ können Sie Segment implementieren die Comparable Schnittstelle und Arrays.sort(points) funktioniert out of the box:

private static class Segment implements Comparable<Segment> { 
    int number, type; 
    Segment(int number, int type) { 
     this.number = number; 
     this.type = type; 
    } 

    @Override 
    public int compareTo(Segment s) { 
     int result = Integer.compare(this.number, s.number); 
     if (result == 0) { 
      result = Integer.compare(this.type, s.type); 
     } 
     return result; 
    } 
}