Με δεδομένο έναν τετράγωνο μήτρα, επιστρέψτε το άθροισμα των διαγωνίων του πίνακα.
Συμπεριλάβετε μόνο το άθροισμα όλων των στοιχείων στην κύρια διαγώνιο και όλων των στοιχείων στη δευτερεύουσα διαγώνιο που δεν αποτελούν μέρος της κύριας διαγώνιου.
Παράδειγμα 1:
Input: mat = [[1,2,3], [4,5,6], [7,8,9]] Output: 25 Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25 Notice that element mat[1][1] = 5 is counted only once.
Παράδειγμα 2:
Input: mat = [[1,1,1,1], [1,1,1,1], [1,1,1,1], [1,1,1,1]] Output: 8
Παράδειγμα 3:
Input: mat = [[5]] Output: 5
Περιορισμοί:
n == mat.length == mat[i].length1 <= n <= 1001 <= mat[i][j] <= 100
Λύση:
public int DiagonalSum(int[][] mat) {
int sum = 0;
int rowS=0,colE=mat[0].Length-1;
for (int i = 0; i < mat.Length; i++)
{
for (int j = 0; j < mat[i].Length; j++)
{
if(i==j || (rowS==i && colE==j))
{
sum+=mat[i][j];
}
}
rowS++;
colE--;
}
return sum;
}Επεξήγηση:
Διαγώνιος από αριστερά προς τα δεξιά, η τιμή του i ισούται με την τιμή j . mat[0,0],mat[1,1],mat[2,2] όλα είναι αριστερό διαγώνιο στοιχείο αλλά αθροιστικά χρειαζόμαστε διαγώνιο στοιχείο από δεξιά προς τα αριστερά οπότε σε αυτήν την περίπτωση πρέπει να ελέγξουμε τις τιμές του i και j .
Για τα στοιχεία 3, 5 και 7, οι τιμές του i, j είναι i=0,j=2 ,i=1,j=1 και i=2,j=0 , εδώ η παρατήρηση είναι i αυξανόμενη τιμή και j η αξία μειώνεται. Χρησιμοποιούμε rowS,colE αυτές οι μεταβλητές στο if condition και μετά την εκτέλεση του εσωτερικού βρόχου for κάνουμε incrementing(rowS) και decrementing(colE).
Πολυπλοκότητα χρόνου:
O(N 2 )
Χρειάζεστε βοήθεια;
Διαβάστε ξανά αυτήν την ανάρτηση, εάν έχετε οποιαδήποτε σύγχυση, διαφορετικά προσθέστε τις ερωτήσεις σας στην Κοινότητα