1

渡されたものとは異なる行列ですべての数値をクラスター化し（1つのクラスター内で同じ値の数値、たとえば5つだけにすることができます）、次のような辞書を返す必要があります。

    {number1:[[(3,4),(4,5)],[]..], number2:...}#I am using Python

行と列を反復処理でき、渡された番号xとは異なる番号を見つけたら、フラッドフィルを開始してクラスターを作成し、訪問した位置を記憶して、同じクラスターが2つになるのを防ぎます。誰かがもっと良いアイデアをもっと早く持っているのだろうか？

例（1以外のすべての数値をクラスター化したい） 渡された値1

2  1  1  2
2  1  2  2 
1  1  3  3

{2：[（0,0）、（1,0）]、[（0,3）、（1,2）（1,3）]、3：[（2,2）、（2 、3）]}

4

2 に答える 2

1

target valueセルの値をとに分類しましょうreplacement value(s)。ここで、 の付いたセルtarget valueが変更したいセルです。のものをクラスター化しますreplacement value(s)。あなたの例では、これらの値はたまたま 1 と (2,3) です。

フラッド フィルの通常のアプリケーションの 1 つは、セルを でセルを に変更するreplacement value(s)ことです。target valueたとえば、ペイント アプリケーションのバケツ フィルツールです。これがユースケースである場合、セルにアクセスするたびにセルの値を変更するだけでよいため、以前にアクセスしたかどうかを覚えておく必要がなくなります。それはあなたのユースケースではないと思います。

方法 #1:辞書を使用する

訪問したセルの (row, col) をキーとして辞書を使用します。(行、列) にアクセスしたかどうかを確認したいので、O(1) 時間複雑度でそれを行うことができます。メソッドは、最初に特定のreplacement valueキーに移動し、リストを反復して (現在の行、現在の列) が存在するかどうかを確認する必要があります。時間の複雑さは O(k) に比例します。ここで、k はリスト内の要素の数です。最悪の場合、O(RxC) になります。ここで、RxC は行列の次元です。

方法 #2: bool 行列を使用する

簡単な別のアプローチは、セル値マトリックスと同じ次元の bool 型のマトリックスを持つことです。セルにアクセスするたびに、True としてマークします。O（1）で、セルがすでにアクセスされているかどうかを確認できます。

最悪の場合、上記の両方のデータ構造の空間複雑度は O(RxC) になります。セル値に対して同じ順序のマトリックスが既にあるので、これで問題ないと思います。

于 2013-01-21T16:39:36.143 に答える
1

numpy.where() の使用を検討しましたか? データを配列に入れることができる場合は、次のように簡単に使用できます。

 import numpy as np
 data=np.array(<some data>)
 np.where(data!=2)

2 に等しくない要素のインデックスを取得します。さらに言えば、次のような直接比較を使用した numpy 配列の作業

 data > 5

比較が真であるブール配列を返します。

 data[data > 5]

おそらく numpy.where() さえ必要としないように、比較が真の値を返します。

于 2013-01-21T16:39:50.763 に答える