在一个二维矩阵中找到相邻的元素

Question

在一个二维矩阵中找到相邻的元素

5

我有一个二维矩阵，其大小为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。

有没有人能帮我提供一种乐观的算法来解决这个问题？

- Rockstart

输入重复的预期结果是什么？ - cuongle

3个回答

4

似乎二维数组中的元素（假设为a [n] [m]）在水平和垂直方向上递增。因此，对于给定的问题，我们需要首先找到该元素的索引。如果我们能以更快的方式找到该元素，则可以优化解决方案。那么问题是如何以高效的方式找到它。

一种方法是取矩阵的中间元素并检查给定元素是否与其相同。

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

如果给定的元素大于中间元素，则我们的解决方案不在矩阵 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 =（总行数）*（总列数）

                _________________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 .

- Imposter

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

- cuongle

@Coung Le：当input没有重复时，index = array.IndexOf(input); 这个方法才有效。 - Rockstart

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matthew Strawbridge · Accepted Answer

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的元素）。