Reduzieren Sie ein Array in C#

Question

In C# Was ist der kürzeste Code zum Abflachen eines Arrays?

Zum Beispiel möchte ich

[[1,2],[2,3],[4,5]] 

in das Array

[1,2,3,4,5] 

ich den kürzesten Weg suchen, dies zu tun.

Answer 1

eine versetzte Anordnung zu einer 1-dimensionalen Array Konvertierung ist einfach und kann in O(n) Zeit und n Raum durchgeführt werden (wo n ist die Summe aus dem 2. Dimension Array Längen), aber in Ihrem Beispiel scheinen Sie doppelte Werte zu entfernen - Das ist kein Verflachen eines Arrays, aber es kann immer noch in O(n) Zeit getan werden, aber wird O(2n) Speicherplatz benötigen, weil Sie eine Hashtabelle für O(1) doppelte Wert Lookups benötigen.

Ein mögliches Problem besteht darin, im Voraus zu wissen, wie viele Elemente im endgültigen Array vorhanden sind. Eine einfache Lösung ist auf eine List<T> und ruft .ToArray() am Ende anzuhängen, aber das in O(2n) Zeit und O(3n) Raum führen wird (aber potentiell wegen List<T> interne Umschichtungen):

Int32[][] jagged = ... 
HashSet<Int32> seen = new HashSet<Int32>(); 
List<Int32> ret = new List<Int32>(); 

for(int i = 0; i < jagged.Length; i++) { 
    for(int j = 0; j < jagged[i].Length; j++) { 
     Int32 val = jagged[i][j]; 
     if(!seen.Contains(val)) { 
      ret.Add(val); 
      seen.Add(val); 
     } 
    } 
} 

return ret.ToArray(); // This takes O(n) time and will allocate O(n) additional space. 

Eine andere Lösung, indem Sie 2 besteht geht selbst: die ersten, die Größe des Ausgangs, dann der zweite Durchlauf zu generieren, um zu bestimmen - was in weniger Kopieren führen wird: ich bin readin

Int32[][] jagged = ... 
HashSet<Int32> seen = new HashSet<Int32>(); 

// Pass 1 
for(int i = 0; i < jagged.Length; i++) { 
    for(int j = 0; j < jagged[i].Length; j++) { 
     Int32 val = jagged[i][j]; 
     seen.Add(val); // HashSet.Add is safe/idempotent 
    } 
} 

Int32[] ret = new Int32[ seen.Count ]; 

// Pass 2 
seen.Clear(); 

Int32 retIdx = 0; 
for(int i = 0; i < jagged.Length; i++) { 
    for(int j = 0; j < jagged[i].Length; j++) { 
     Int32 val = jagged[i][j]; 
     if(!seen.Contains(val)) { 
      ret[++retIdx] = val; 
      seen.Add(val); 
     } 
    } 
} 

return ret; 

Answer 2

Vielleicht: genau O(2n) Zeit und genau O(2n) Raum g "kürzester Code" der falsche Weg, aber ich würde LINQ SelectMany und Distinct mit propose:

var values = new[] 
{ 
    new[] { 1, 2 }, 
    new[] { 2, 3 }, 
    new[] { 4, 5 }, 
}; 

var flattenedUniqueValues = values.SelectMany(x => x).Distinct();