Cで配列を平坦化する

Question

C＃で配列を平坦化する最短のコードは何ですか？例えば

、私はそうする最短の方法を探しています配列

[1,2,3,4,5] 

に

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

をしたいです。 1次元配列に千鳥配列の変換

Answer 1

が簡単で、（nが第二次元配列の長さの合計である）O(n)時間とnスペースで行うことができ、しかし、あなたの例では、重複する値を削除するように見えます - それは配列を平坦化していませんが、O(n)時にも実行できますが、O(1)重複値の検索のハッシュテーブルが必要であるため、O(2n)スペースが必要です。

最終アレイにいくつの要素が存在するかを事前に知ることには、考えられる問題があります。簡単な解決策はList<T>と終わりに.ToArray()を呼び出すに追加することですが、それはO(2n)時間とO(3n)スペースになります（ただし、潜在的List<T>内部再配分のために）します：

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. 

別の解決策は、2を実行して存在します出力の大きさを決定するために最初、それを生成するために、その後、第二のパス - レスコピーになりますどの：あなた自身を渡し、正確O(2n)時間と正確にO(2n)スペース：

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

は、たぶん私はreadinよグラム「最短コード」間違った方法が、私はLINQ SelectManyとDistinctを使用して提案する：

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

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