Ein abnehmendes Tripel ist definiert als eine Menge von 3 Werten {a, b, c}, die von links nach rechts abnehmen so dass a> b> c.Anzahl der Gruppen bestehend aus 3 abnehmenden Werten in Ganzzahl-Array (unter 0 (n^3) Zeit)
Wie man die Anzahl dieser Tripel in einem Array von ganzen Zahlen, wo die Indizes der Tripel {i, j, k}, so mehren sich, dass i < j < k finden konnten.
Betrachten wir zum Beispiel die folgenden Beispiele:
{4, 5, 2, 1}
2 decreasing triples: {4, 2, 1} and {5, 2, 1}
{6, 1, 2, 4, 5, 3}
2 decreasing triples: {6, 5, 3} and {6, 4, 3}
{5, 4, 3, 2, 1}
10 decreasing triples:
{5, 4, 3}, {5, 4, 2}, {5, 4, 1}, {5, 3, 2}, {5, 3, 1},
{5, 2, 1}, {4, 3, 2}, {4, 3, 1}, {4, 2, 1}, {3, 2, 1}
Der O (n^3) Lösung ist trivial natürlich; hier ist eine Implementierung in Java: * Anmerkung: die Arrays von Long-Positionen sind, aber das ist eine geringe Implementierungsdetail
public static long countTriples(long[] measurements)
{
// O(n^3)
long count = 0L;
for(int i = 0; i < measurements.length; i++)
{
for(int j = i + 1; j < measurements.length; j++)
{
if (measurements[j] < measurements[i])
{
for(int k = j + 1; k < measurements.length; k++)
{
if (measurements[k] < measurements[j])
{
count++;
}
}
}
}
}
return count;
}
}
ich eine O (n) Methode begann abnehmend Tripel zu lokalisieren; es hat Triples erfolgreich identifiziert, aber ich konnte es nicht richtig zählen, wenn der Mittelwert eines gegebenen Tripel an mehr als einem beteiligt war. Hier ist, was ich von diesem Recht habe jetzt:
public static long countTriples(long[] measurements)
{
ArrayList<Long> greaterOnLeft = new ArrayList<Long>();
ArrayList<Long> lessOnRight = new ArrayList<Long>();
HashSet<Long> min = new HashSet<Long>();
min.add(measurements[measurements.length - 1]);
HashSet<Long> max = new HashSet<Long>();
max.add(measurements[0]);
for(int i = 0; i < measurements.length; i++)
{
min.add(measurements[measurements.length - i - 1]);
max.add(measurements[i]);
System.out.println("max: " + max + ", min: " + min);
for(long n : max)
if (measurements[i] < n) greaterOnLeft.add(measurements[i]);
for(long n : min)
if (measurements[measurements.length - i - 1] > n) lessOnRight.add(measurements[measurements.length - i - 1]);
}
long count = 0;
for(long n : greaterOnLeft)
{
if(lessOnRight.contains(n)) count++;
}
return count;
}
Die Idee für diesen Ansatz aus einer HashSet Methode kam zum Lokalisieren der Mitte Indizes solchen tripples von diesem Posten:
How to find 3 numbers in increasing order and increasing indices in an array in linear time
Sie haben einen Algorithmus in der Frage, die Sie verlinken auf: dies kann in O (n^2) Zeit eher triviale Weise gelöst werden http://stackoverflow.com/questions/10008118/how-to-find- 3-Numbers-in-ordering-order-indices-in-array-in. Es sieht so aus, als ob du wirklich darum bittest, deinen Code zu debuggen, aber es gibt keinen Hinweis darauf, was dein Problem anders ist als "es zählt nicht". –
Nein, dieser Algorithmus findet einzelne Instanzen, keine Anzahl aller Vorkommen. – thedevelop3r
Wenn ich Vorkommen mit dieser Methode zähle, können Indizes, die die Mitte von mehreren Tripeln bilden, nicht korrekt berücksichtigt werden. Ich hatte die Ergebnisse ursprünglich in einem HashSet gespeichert, aber ich erkannte, dass ich einen Weg brauchte, um diese Tripel mit demselben Mittelwert zu verfolgen; Ich sehe keine Möglichkeit, das zu tun. – thedevelop3r