Finden Sie benachbarte Elemente in einer 2D-matrix

Ich habe eine 2-dimensionale matrix der Ordnung m *n

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

Aus dieser, da ein element , muss ich schreiben, eine Methode, die zurückgibt, die angrenzenden Elemente.
Tüpfel sind entweder horizontal, vertikal oder Diagonal benachbart sind.

Beispielsweise benachbarte element 01 00,02,10,11,12
angrenzenden element der 00 01 ,10,11
benachbarte element 11 ist 00,01,02,10,12,20,21,22

Kann jemand mir helfen mit einer optimistischen Algorithmus, um dieses Problem zu lösen?

Was erwartete Ergebnis Eingabe wiederholt werden?

InformationsquelleAutor Rockstart | 2012-09-18

algorithm c#matrix

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)

Daraus ergibt sich die Antwort:
3
4
7
11
12
(die Elemente neben der 8).

Sie Durchlaufen alle Zeilen und Spalten für jedes element. ES beeinflusst die Leistung, wenn die matrix zu groß ist
Nein, ich bin nicht. Ich bin das Durchlaufen der neun Elemente (3 x 3 block), der uns interessiert.
Du hast Recht. Vielen Dank:-)
Du bist herzlich willkommen. Ich Tat, verwenden Sie so etwas wie foreach (int j in new[] { row - 1, row, row + 1 }) deutlicher machen, dass es eine Feste Liste, aber entschied sich für die einfachere und schnellere for loop statt.

InformationsquelleAutor Matthew Strawbridge

4

Scheint es Elemente im 2d-array(eine[n][m]) sind zunehmend horizontal und vertikal . Also für die gegebene Frage, die wir brauchen, um zu finden, die den index des Elements zuerst. Also, wenn wir finden das element in schnelleren Weg, dann können wir optimieren die Lösung .
Die Frage ist, wie finden wir es in einer effizienten Art und Weise.
Ein Ansatz ist nehmen Sie das mittlere element der matrix und überprüfen element mit

wenn element kleiner als das mittlere element, dann ist unsere Lösung liegt in der matrix a[0][0] bis a[n/2][m/2], weil alle Elemente nach rechts und unten größer sind als die Mitte (da element ist kleiner als das mittlere element), so reduzieren wir unseren Suchraum von a[n][m] zu a[n/2][m/2], die ein Viertel der ursprünglichen Größe.

wenn bestimmtes element größer als das mittlere element, dann ist unsere Lösung liegt nicht in den Matrizen a[0][0] bis a[n/2][m/2], weil alle Elemente nach Links und oben sind kleiner als Mitte (da element größer als das mittlere element), so dass unsere Suche Raum ist insgesamt array minus a[0][0] bis a[n/2][m/2], die drei Viertel der ursprünglichen Größe.
Insgesamt array minus a[0][0] bis a[n/2][m/2] bedeutet ,gibt es drei rekursive Aufruf mit einem array-index
```
    --------->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)
```
Nun rekursiv aufrufen der gleichen Funktion basiert auf unserem Suchraum.

Zeit Komplexität unserer Funktion wie folgt .
HINWEIS: In der Zeit-Funktion n repräsentiert die Anzahl der element, nicht aber keine Zeilen erwähnt .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
```
so out-Zeit-Funktion wird

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) 
```
Aber T(1)=1 (raten gegeben elemet gefunden in array)
```
so  n/(4power(i))=1
====> n=2power(2*i)
====> n=2power(2*i)
```
Reden log zur Basis 2 auf beiden Seiten (log[n])/2=i
====> ich=log(sqrt(n))

Substitution von Gleichung 1 erhalten wir T(n)=3power(log[sqrt(n)])

Also nach der Suche nach dem element mit dem index finden wir es Nachbarn .
Sagen wir element in a[i][j] dann drucken
```
 {
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]
}
```
zur Verfügung gestellt
```
 0<i<n and 0<j<n .
```
InformationsquelleAutor Imposter

Nehme an, Sie haben matrix string [n,m] können Sie das Ergebnis durch Abflachung der matrix, im folgenden Beispielcode:

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

Le: index = array.IndexOf(Eingabe); dies funktioniert nur, wenn die Eingabe nicht wiederholt.

InformationsquelleAutor cuongle

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.