5

m*n次の2次元行列があります

00 01 02 03 ....0n
10 11 12 13 ....1n
20 21 22 23 ....2n
..
m0 m1 m2  m3 ...mn

これから、要素が与えられた場合、隣接する要素を返すメソッドを作成する必要があります。隣接する要素は、水平、垂直、または対角線上に隣接しています。

たとえば、01の隣接する要素は00,02,10,11,12です。00の隣接する要素は01,10,11です。11の隣接する要素は00,01,02,10,12,20,21,22です。

誰かがこれを解決するための楽観的なアルゴリズムで私を助けることができますか？

4

3 に答える 3

9 
public static IEnumerable<T> AdjacentElements<T>(T[,] arr, int row, int column)
{
    int rows = arr.GetLength(0);
    int columns = arr.GetLength(1);

    for (int j = row - 1; j <= row + 1; j++)
        for (int i = column - 1; i <= column + 1; i++)
            if (i >= 0 && j >= 0 && i < columns && j < rows && !(j == row && i == column))
                yield return arr[j, i];
}

...

var arr = new[,] { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} };

var results = AdjacentElements(arr, 1, 3);

foreach(var result in results) 
    Console.WriteLine(result)

これにより、次の答えが得られます：3 4 7 11 12（8に隣接する要素）。

于 2012-09-18T08:28:39.000 に答える
4

2次元配列（be a [n] [m]）の要素が水平方向および垂直方向に増加しているようです。したがって、与えられた質問に対して、最初に要素のインデックスを見つける必要があります。したがって、要素をより迅速に見つけることができれば、ソリューションを最適化できます。問題は、それを効率的な方法でどのように見つけるかです。1つのアプローチは、マトリックスの中央の要素を取得し、それを使用して特定の要素をチェックすることです。

与えられた要素が真ん中の要素よりも小さい場合、右下のすべての要素が真ん中よりも大きいため、解は行列a[0][0]からa[n/ 2] [m /2]にあります（与えられた要素が小さいため）中央の要素よりも）、検索スペースをa[n][m]から元のサイズの4分の1であるa[n/ 2] [m/2]に縮小しました。

与えられた要素が真ん中の要素より大きい場合、左上のすべての要素が真ん中よりも小さいため、解は行列a[0][0]からa[n/ 2] [m /2]にありません（与えられた要素は中央の要素よりも大きい）、したがって、検索スペースは、配列全体からa[0][0]を引いたものからa[n/ 2] [m / 2]になり、元のサイズの4分の3になります。 配列の合計からa[0][0]からa[n/ 2] [m / 2]を引いたものは、配列インデックスを使用した3つの再帰呼び出しがあることを意味します

    --------->a[0][m/2](start index) to a[n/2][m](end index)  
    --------->a[n/2][0](start index) to a[n][m/2](end index)
    --------->a[n/2][m/2](start index) to a[n][m](end index)

次に、検索スペースに基づいて同じ関数を再帰的に呼び出します。

関数の時間計算量は次のようになります。 注：時間内関数nは要素の総数を表しますが、前述のように行の数は表しません。n =（no_of_rows）*（no_of_columns）

                _________________T(n/4)  if given element is less than middle of the array.
               / 
              /
T(n)==========------------------- 1 if n=1 (if element found)
              \
               \_________________3T(n/4) if given element is greater than middle element of array

したがって、タイムアウト関数は

T（n）= 3T（n / 4）またはT（n）= T（n / 4）

In worst case T(n)=3T(n/4)
               T(n)=3{3T(n/4)}
               T(n)=3power(i)T(n/(4)poweri)     equation------> (1)

しかし、T（1）= 1（与えられた要素が配列にあると推測する）

so  n/(4power(i))=1
====> n=2power(2*i)
====> n=2power(2*i)

両側のベース2にログを話します(log[n])/2=i ====>i= log（sqrt（n））

式1を代入すると、T（n）= 3power（log [sqrt（n）]）が得られます。

したがって、インデックスを使用して要素を見つけた後、隣接する要素を見つけることができます。a [i] [j]で見つかった要素を考えて、次のように出力します。

 {
a[i-1][j-1],
a[i-1][j],
a[i-1][j+1],
a[i][j-1],
a[i][j+1],
a[i+1][j-1],
a[i+1][j],
a[i+1][j+1]
}

提供された

 0<i<n and 0<j<n .
于 2012-09-18T09:34:17.227 に答える
2

の行列があると仮定するとstring [n,m]、行列を平坦化することで結果を得ることができます。以下のサンプルコードは次のとおりです。

var array = matrix.Cast<string>()
                       .ToList();

var index = array.IndexOf(input);

var indexList = new List<int>() {
    index - n - 1, 
    index - n, 
    index - n + 1,
    index - 1, 
    index + 1, 
    index + n - 1, 
    index + n , 
    index + n + 1};

var result = array.Where((item, i) => indexList.Contains(i));
于 2012-09-18T07:00:00.853 に答える