c# - 查找二维矩阵中的相邻元素

Question

我有一个 m *n 阶的二维矩阵

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

有人可以帮我用一种乐观的算法来解决这个问题吗？

Answer 1

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)

This yields the answer: 3 4 7 11 12 (the elements adjacent to the 8).

Answer 2

二维数组中的元素（be a[n][m]）似乎在水平和垂直方向上增加。所以对于给定的问题，我们需要首先找到元素的索引。因此，如果我们能以更快的方式找到元素，那么我们就可以优化解决方案。问题是我们如何以有效的方式找到它。一种方法是取矩阵的中间元素并用它检查给定元素

如果给定元素小于中间元素，那么我们的解决方案在于矩阵 a[0][0] 到 a[n/2][m/2] 因为右边和下面的所有元素都大于中间（因为给定元素小于比中间元素），所以我们将搜索空间从 a[n][m] 减少到 a[n/2][m/2]，这是原始大小的四分之一。

如果给定元素大于中间元素，那么我们的解决方案不在于矩阵 a[0][0] 到 a[n/2][m/2] 因为左边和上面的所有元素都小于中间（因为给定元素是大于中间元素），所以我们的搜索空间是总数组减去 a[0][0] 到 a[n/2][m/2]，它是原始大小的四分之三。 总数组减去 a[0][0] 到 a[n/2][m/2]意味着，将有三个带有数组索引的递归调用

    --------->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)

双方对话日志到base 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 .

Answer 3

假设你有 的矩阵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));