2つの同一配列が1つの2次元配列に存在するかどうかをチェックする方法は？ [Swift]

Question

もし私が[[1,2,3]、[3,2,1]、[4,9,3]]のような2次元配列を持っていれば、この配列内には[1,2,3]と[3,2,1]という2つの同一の配列が存在します。どうすればこれを達成できますか？

すべてのあなたの答えをありがとう、私はleetCode threeSumの問題に焦点を合わせていたので、私はコメントを残さなかった。しかし、私はプログラミングのnoobie以来、私の答えは時間制限を超えて..実際には、複製された配列を見つけて、すべての重複を削除し、多次元配列内の唯一のユニークな配列を残したい。私はオレグの答え@に基づいていくつかの余分なコードを追加して、私はここに私の機能を置くだろうと思っている：私の心に来る

func removeDuplicates(_ nums: inout [[Int]]) -> [[Int]]{ 
    let sorted = nums.map{$0.sorted()} 
    var indexs = [Int]() 

    for (pos,item) in sorted.enumerated() { 
     for i in pos+1..<sorted.count { 
      if item == sorted[i] { 
       if nums.indices.contains(i){ 
        indexs.append(i) 
       } 
      } 
     } 
    } 
    indexs = Array(Set<Int>(indexs)) 
    indexs = indexs.sorted(by: {$0 > $1}) 

    for index in indexs{ 
     nums.remove(at: index) 
    } 

    return nums 
} 

Answer 1

私のソリューションは非常に簡単で分かりやすいです。

let input = [[1,2,3], [3,2,1], [4,9,3]] 

まず、ネストされた配列のすべての要素をソートします。 （それは私たちにもう少し効率を与えます）。

let sorted = input.map{$0.sorted()} 

私たちは各要素を比較する必要があります。

for (pos,item) in sorted.enumerated() { 
    for i in pos+1..<sorted.count { 
     if item == sorted[i] { 
      print(input[pos]) 
      print(input[i]) 
     } 
    } 
} 

出力：

[1, 2, 3] 
[3, 2, 1] 

Answer 2

一つのシンプルで簡単な強引なアプローチがある：

1. 反復オーバー各行の値をソートします。したがって1,2,3は123になり、3,2,1も1,2,3になります。
2. これをキー値ペア、つまりマップに格納します。キーは123になり、配列1,2,3または3,2,1にマップされます。

注： - あなたのキーは、ソートされたすべての要素がカンマなしの文字列として結合されています。

このようにして、2次元配列内にどのように配列のペアが存在するかが分かります。

Answer 3

順列ハッシュ法を用いて、非常に効率的なアルゴリズムがあります。

1）すべての要素が負でないように2次元配列を前処理する。各サブ配列A： で2）サブアレイAのすべてのインデックスiを用いてhash [A] = sum（base^A [i] |）を計算します（すべての要素から最小の要素を減算します）。ベースを非常に大きな素数（例えば1e9 + 7）にする。ここでは加算と乗算のみを使用するため、計算時に整数オーバーフローの問題を無視することができます。

3）各サブアレイの配列「ハッシュ」があります。配列に2つの同一のサブ配列がある場合は、同じハッシュコードを持つ必要があります。等しいハッシュコードを持つすべてのサブアレイのペアを検索します（ハッシュを再度使用するか、並べ替えるなど...）。

4）各ペアについて、これらのサブアレイが実際に一致するかどうかをもう一度確認します（ソートと比較、...何でも）。実際に一致する2つのサブ配列を見つけることができる場合はtrue、そうでない場合はfalseを返します。

理論的には非常に遅いが実際にはこのメソッドは非常に高速に実行されます。これは、ハッシュ・ステップが検索スペースの大半を切り取るためであり、このハッシュ関数は非常に強力です。 99.99％が存在すれば、同じハッシュコードを持つ対応するサブアレイのペアが実際に一致することは間違いありません。