Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Liste - Zahlen ergänzen bzw. fehlende Zahlen erkennen
galagher - Sa 18.04.15 16:41
Titel: Liste - Zahlen ergänzen bzw. fehlende Zahlen erkennen
Hallo!
Ich habe eine ListBox mit Zahlen, zB:
Ich möchte nun diese Liste durchlaufen und es soll dabei erkannt werden, dass 003 fehlt, dies soll in eine andere Liste geschrieben werden.
Es kann auch vorkommen, das zwei oder mehr Zahlen fehlen, auch das soll erkannt werden:
Alle fehlenden Zahlen möchte ich in einer anderen Liste haben, in diesem Beispiel also 011, 012, 013, dann ab 015 bis 020.
Ein Logikproblem, und ich komme auf keine Lösung!
Th69 - Sa 18.04.15 17:24
Hallo,
was ist daran so schwer? Wenn die Zahlen in der Liste sortiert sind (ansonsten eben zuvor sortieren), dann in einer Schleife jeweils zwei aufeinanderfolgende Zahlen vergleichen, und wenn die Differenz größer als 1 ist, dann die fehlenden Zahlen (wiederum eine Schleife) in die andere Liste schreiben.
Ralf Jansen - Sa 18.04.15 17:47
Die obligatorische, dem Verständnis nicht helfende, LINQ Antwort ;)
C#-Quelltext
1: 2:
| List<Int32> list = new List<int>() { 9, 10, 14, 21 }; List<Int32> missingValues = Enumerable.Range(list.Min(), list.Max() - list.Min() + 1).Except(list).ToList(); |
galagher - Sa 18.04.15 19:32
Th69 hat folgendes geschrieben : |
was ist daran so schwer? |
Es mir vorzustellen! :nixweiss:
Th69 hat folgendes geschrieben : |
dann in einer Schleife jeweils zwei aufeinanderfolgende Zahlen vergleichen, und wenn die Differenz größer als 1 ist, dann die fehlenden Zahlen (wiederum eine Schleife) in die andere Liste schreiben. |
Also zwei Schleifen, wobei die zweite, die schreibt, innerhalb der ersten liegt?
Ich gehe also von 0 bis Count-2, subtrahiere das jeweils nächste Item vom aktuellen Item, wenn > 1, schreibe Zahl. Das müsste ich dann in einer zweiten Schleife machen, ich weiss aber nicht, wie!
Ich schreibe die Zahlen erstmal sortiert in eine TStringList.
Aber so wird immer nur eine Zahl geschrieben, zwei fehlende nicht:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8:
| for i := 0 to L.Count-2 do begin if StrToInt(L[i+1]) - StrToInt(L[i]) > 1 then begin n := StrToInt(L[i])+1; L1.Add(IntToStr(n)); end; end; |
Palladin007 - Sa 18.04.15 20:50
Warum so kompliziert mit Vergleichen von zwei Zahlen?
Es reicht doch schon, einfach hoch zu zählen und zu schauen, ob eine Zahl da ist oder nicht.
C#-Quelltext
1: 2: 3: 4: 5: 6: 7: 8:
| var list = new List<int>() { 1,5,8,4 }; var missingValues = new List<int>();
for (int i = list.Min() + 1; i < list.Max(); i ++) { if (!list.Contains(i)) missingValues.Add(i); } |
Natürlich muss die Ausgangsliste dazu ziemlich oft durchsucht werden.
Ich weiß nicht, wie performant das ist, wenn das ein Problem darstellen sollte, geht ja auch noch diese Möglichkeit:
C#-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:
| var list = new List<int>() { 1,5,8,4 }; var missingValues = new List<int>();
var number = list.Min(); for (int i = 0; i < list.Count; ) { number++;
if (list[listIndex] == number) i++; else missingValues.Add(number); } |
Das ist kein Delphy, ich hoffe, Du verstehst den Code trotzdem, ist nichts allzu kompliziertes dabei.
list.Min() und
list.Max() geben den jeweils kleinsten bzw. höchsten Wert aus der Liste zurück, die restlichen Methoden decken sich glaube ich alle mit Delphy.
list.Min() und
list.Max() kannst Du ja auch durch deinen Mindest- und Höchst-Wert ersetzen, z.B. 0 und 100.
Bei der Antwort von Ralph sieht das ja etwas anders aus :D
Enumerable.Range erstellt eine vollständige Zahlen-Liste im angegeben Bereich (durch
list.Min() und
list.Max() - 1 vorgegeben) und sucht anschließend mit
Except(list) die Unterschiede zur Ausgangsliste heraus, was in diesem Fall die fehlenden Zahlen sind. Das
ToList() am Ende steht dort, da viele LINQ-Methoden
IEnumerable zurück geben, was grundsätzlich keine Liste ist und erst zu einer gemacht werden muss.
C# - Sa 18.04.15 20:57
So wie ich es verstanden habe, sind deine Zahlen als String vorhanden und nicht als Integer. Ich kann leider nur C#, ich hoffe ich habe den Code genug erklärt.
C#-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34:
| static void Main(string[] args) { List<string> sampleList = new List<string> {"001", "002", "004", "005", "008", "009", "015"}; List<string> missingList = new List<string>();
for (int i = 1; i < sampleList.Count; i++) { int lower = int.Parse(sampleList[i - 1]);
int upper = int.Parse(sampleList[i]);
for (lower++; lower < upper; lower++) { missingList.Add(string.Format("{0:000}", lower)); } }
Console.WriteLine("Original sample list:"); foreach (string s in sampleList) Console.WriteLine(s);
Console.WriteLine("\nMissing numbers:"); foreach (string s in missingList) Console.WriteLine(s);
Console.ReadKey(); } |
Die Ausgabe des Codes:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:
| Original sample list: 001 002 004 005 008 009 015
Missing numbers: 003 006 007 010 011 012 013 014 |
/// EDIT
Um Ralf zu ergänzen hier nochmal das gleiche in Linq:
C#-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:
| List<string> sampleList = new List<string> { "001", "002", "004", "005", "008", "009", "015" }; List<string> missingList = Enumerable.Range(sampleList.ConvertAll(s => int.Parse(s)).Min(), sampleList.ConvertAll(s => int.Parse(s)).Max() - sampleList.ConvertAll(s => int.Parse(s)).Min()) .Select(i => string.Format("{0:000}", i)) .Except(sampleList) .ToList();
Console.WriteLine("Original sample list:"); foreach (string s in sampleList) Console.WriteLine(s);
Console.WriteLine("\nMissing numbers:"); foreach (string s in missingList) Console.WriteLine(s); |
Palladin007 - Sa 18.04.15 21:51
Ich würde es mir da ja eher einfach machen und die Ausgangsliste in eine Int-Liste übertragen. Das lässt sich simpel mit einer Schleife lösen.
Der Rest danach ist so, wie vorher beschrieben.
Was .NET angeht:
Es gibt IComparer, dann erstelle ich mir eben einen IComparer, der strings als Zahlen behandelt und entsprechend vergleicht.
Ich meine, dass alle benötigten Methoden auch eine Überladung anbieten, die IComparer entgegen nimmt, oder zumindest eine Func, die entsprechendes erledigt.
Aber auch unter .NET würde ich einfach die String-Liste in eine Int-Liste schreiben, das ist bedeutend einfacher ^^
galagher - Sa 18.04.15 22:22
Ich danke euch allen für eure Tipps und die rasche Hilfe, mich verwirren nur "obere Grenze" und "untere Grenze" etwas, wie auch Min() und Max(). Jedenfalls muss der schreibende Teil des Ganzen eine Schleife sein, oder, so habe ich es jetzt gelöst, man aktualisiert bei jedem Schreiben der fehlenden Zahlen die zu lesende Liste, dazu habe ich alles in ein
repeat/until gepackt.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
| c := liste1.count; x := c;
repeat for i := 0 to liste1.count-2 do begin if item+1 - item > 1 then begin c := liste1.count; end; end; Inc(x); until x >= c; |
Ist eine Schleife und klappt!
Zur Frage nach der Performance - bei 001 bis maximal 999 ist diese wohl vernachlässigbar!
Zu C (genauer: C++) - lange ist's her, über 20 Jahre! ja, ich verstehe den Code im Wesentlichen, nur fällt mir auf: Bei Delphi kann man den Zähler einer for-Schleife nicht erhöhen, bei C geht das scheinbar (ich erinnere mich nicht mehr):
C#-Quelltext
1: 2: 3: 4: 5: 6:
| for (int i ... { ... i++; ... } |
Th69 - So 19.04.15 09:30
Hallo,
bei deinem ersten Quellcode fehlt noch die innere Schleife:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8:
| for i := 0 to L.Count-2 do begin nLow = StrToInt(L[i]); nHigh = StrToInt(L[i+1]); if nHigh - nLow > 1 then for j := nLow+1 to nHigh-1 do L1.Add(IntToStr(j)); end; |
galagher - So 19.04.15 18:50
Th69 hat folgendes geschrieben : |
bei deinem ersten Quellcode fehlt noch die innere Schleife: |
So ist's kürzer und funktioniert ebenfalls korrekt!
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!