folgendes Bild Betrachten, ist es ein Array von Elementen:Wie finden Sie die Verbindungen oder Beziehungen zwischen Elementen in einem Array?
Die Elemente in dem Array durch ein Attribut sortiert werden genannt id (die Zahl in den schwarzen Kreis)
Das Attribut id ist einzigartig.
Jedes Element hat zwei zusätzliche Attribute (in Klammern innerhalb des Kreises): from und to
Jeder Artikel ist verbunden oder zum anderen durch die from und to Attribute verwandt. Beispiel (nicht im obigen Bild):
Using kind of python syntax:
{id:1, from:a, to:b} --> {id:2, from:b,to:c} --> {id:3, from:c, to:a}
Denken Sie an das obige Beispiel als eine kreisförmige verkettete Liste.
Es kann Elemente geben, die nicht mit anderen verknüpft sind (z. B. das Element mit id = 3-).
Die Eingabe ist die id eines beliebigen Elements innerhalb des Arrays.
Der Algorithmus sollte eine der folgenden Ergebnisse ab:
- ein Array von Arrays.
- Eine Reihe von kreisförmigen verknüpften Listen.
Basierend auf dem angezeigten Bild, wobei Beispiele die erwartete Ausgabe sind:
1.- die id = 7 Gegeben ist das erwartete Ergebnis:
An array containing this single array (or its equivalent circular linked list).
That is, the items connected by the blue line.
If the items in the inner array are rotated by N, it's ok.
output = [
[
{id:7, from:m, to:k},
{id:8, from:k, to:i},
{id:10, from:i, to:b},
{id:2, from:b, to:e},
{id:4, from:e, to:h},
{id:1, from:h, to:l},
{id:6, from:l, to:m}
]
]
2.- die id = 2 Angesichts der erwartetes Ergebnis ist:
An array containing two arrays (or their equivalent circular linked list).
That is, the two collections of items connected by the red and the blue line.
If the items in the inner arrays are rotated by N, it's ok.
output = [
[
{id:2, from:b, to:e},
{id:5, from:e, to:g},
{id:9, from:g, to:i},
{id:10, from:i, to:b}
],
[
{id:2, from:b, to:e},
{id:4, from:e, to:h},
{id:1, from:h, to:l},
{id:6, from:l, to:m},
{id:7, from:m, to:k},
{id:8, from:k, to:i},
{id:10, from:i, to:b}
]
]
Also, die Fragen sind:
Was könnte der mögliche Algorithmus und die Datenstruktur sein, um dieses Problem zu lösen?
Dies sieht verdächtig wie Hausaufgaben oder eine Codierung Herausforderung. Können Sie die Motivation hinter dem Versuch erklären, diese Lösung zu lösen? Es kann helfen, Ihren Algorithmus und Ihre Datenstruktur zu bestimmen. –
Hey @ karnesJ.R, nein, das sind keine Hausaufgaben, und ja ... das hört sich nach einer Kodierungsherausforderung an, aber auch nicht. Ich habe eine App, wo Leute über Orte schreiben, wo sie leben und wohin sie wollen. Also könnte dieser Algorithmus ihnen helfen, diese Orte zu finden. –
Nun, das erste, was Sie tun müssen, ist Ihre Datenstruktur zu verstehen. Was Sie haben, ist ein gerichteter Graph. Es gibt ein fantastisches Werkzeug zur Zykluserkennung in SAGES Grafikbibliothek und SAGE arbeitet mit Digraphen. Vielleicht möchten Sie beginnen, indem Sie dort suchen. Wenn es eine praktische Anwendung ist, die echte Dinge tut, gibt es keinen Grund, das Rad neu zu erfinden. –