Anzahl der Elemente, die eine Beziehung

Question

Gegeben seien zwei Arrays erfüllen:

2 5 6 4 3 7 1 
5 1 6 2 3 7 4 

zählen die Anzahl Elemente x, y, die die Bedingung erfüllen, daß, bevor xy in beiden Arrays ist.

---

Fortschritt bisher:

sortieren Arrays durch ihre Indizes. Für das Beispiel wäre dies:

     object: 1 2 3 4 5 6 7 
indexes in the first array: 6 0 4 3 1 2 5 
indexes in the secnod array: 1 3 4 6 0 2 5 

und vergleichen Sie jedes Tupel mit einem anderen. Wenn das Tupel a entweder beide Indizes niedriger oder höher als das Tupel b aufweist, erhöhen Sie die Anzahl der Elemente, die die Bedingung erfüllen.

Dies hat die Zeitkomplexität von (N^2)/2, also O (N^2), was zu langsam ist. Ich verstehe, dass es keine bessere Worst-Case-Szenario-Komplexität geben kann, aber ich bin hauptsächlich am Durchschnittsergebnis interessiert. Also: Gibt es einen besseren Weg/Algorithmus?

Ich dachte über die Verwendung transitiver Eigenschaften (wenn sowohl (x,y) und (y,z) die Bedingung erfüllen, dann (x,z) erfüllt es auch), aber ohne Glück.

---

Testfälle

Für Arrays:

2 5 6 4 3 7 1 
5 1 6 2 3 7 4 

Die Paare, die die Bedingung erfüllen, sind:

(5,1) (2,3) (2,4) (2,7) (5,3) (6,3) (3,7) (5,4) (6,4) (5,6) (5,7) (6,7) 

Für Arrays:

1 2 3 4 5 6 7 
1 2 3 4 5 6 7 

Die Paare, die die Bedingung erfüllen, sind:

(1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (2,3) (2,4) (2,5) (2,6) (2,7) (3,4) (3,5) (3,6) (3,7) (4,5) (4,6) (4,7) (5,6) (5,7) (6,7) 

Answer 1

ich sehr genossen haben über dieses Problem nachzudenken. Es fühlt sich an wie ein CS-Hausaufgabe-Problem, also werde ich versuchen, die Konzepte zu berühren, ohne alles zu lösen.

The Beach Boys Prinzip

Ein Begriff, mein Kalkül Lehrer verwendet und eigentlich ein sehr anwendbar Problem Technik zu lösen. Grundsätzlich, wenn Sie ein schwieriges Problem haben, sagen Sie "wäre es nicht schön, wenn ...", und sehen, ob es etwas gibt, das die Dinge leichter machen würde. Wenn ja, sehen Sie, ob Sie das machen können.

In diesem Fall wäre es nicht nett, wenn das obere Array bestellt wurde und nur [1, 2, 3 ...]? Das würde das Lösen dieses Problems so viel einfacher machen, da es ein Zwei-Array-Problem in ein Ein-Array-Problem verwandelt.

Nun, es kann so sein! Sie können eines dieser Probleme in eines mit einem geordneten ersten Array abbilden.

Das erste Beispiel, die Sie aufgelistet:

2 5 6 4 3 7 1 
5 1 6 2 3 7 4 

ich argumentieren, dass das Problem, das oben entspricht unten auf das Problem:

1 2 3 4 5 6 7 
2 7 3 1 5 6 4 

Mappings

ich nur eine einfache Chiffre Substitution von 2-> 1 5-> 2 6-> 3 4-> 4 3-> 5 7-> 6 1-> 7 (Warum diese bestimmte Zuordnung?). Dies lässt die zugrundeliegende Struktur des Problems gleich. Sie können dies lösen und dann Ihre Zuordnung rückgängig machen.

Sie werden feststellen, dass diese Technik, ein Problem in ein einfacheres Problem zu mappen, häufig in der Informatik auftritt, besonders in Ihren Algorithmen und Berechnungsklassen.

Sie haben nun ein einzelnes Array Problem alle Paare zu finden:

2 7 3 1 5 6 4 

Die Zeitkomplexität dieses ich den Leser ein, eine Übung verlassen.

P.S. Vergessen Sie nicht die zeitliche Komplexität des Rückgängigmachens Ihres Mappings. Manchmal löst man ein Problem, da man leicht herausfinden kann, dass das Erstellen und Dekonstruieren des Mappings extrem teuer ist und man zurück zum Zeichenbrett gehen muss.