مصفوفة قطري مجموع حل Leetcode


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي
مجموعة مصفوفة

المشكلة بيان

في المصفوفة مشكلة مجموع قطري مربع البخور من الأعداد الصحيحة. علينا حساب مجموع جميع العناصر الموجودة في أقطارها ، أي العناصر الموجودة في القطر الأساسي وكذلك القطر الثانوي. يجب حساب كل عنصر مرة واحدة فقط.

مثال

mat = [[1,2,3],
       [4,5,6],
       [7,8,9]]
25

التفسير:

مجموع الأقطار: 1 + 5 + 9 + 3 + 7 = 25
لاحظ أن حصيرة العنصر [1] [1] = 5 تُحسب مرة واحدة فقط

mat = [[1,1,1,1],
       [1,1,1,1],
       [1,1,1,1],
       [1,1,1,1]]
8

التفسير:

Diagonals sum: (1+1+1+1)+(1+1+1+1)=8.

الرسالة

مصفوفة قطري مجموع حل Leetcode

في مصفوفة مربعة معينة ، علينا فقط إضافة العناصر القطرية وإرجاع مجموعها.
دعنا نرى ما سيكون نمط المؤشرات في المصفوفة للعناصر القطرية. أولاً ، إذا رأينا على القطر الأساسي ، فسيكون العنصر الأول في الفهرس i = 0 ، و j = 0 والعنصر التالي على (i + 1 ، j + 1). وبالمثل ، سيكون العنصر الأخير في الفهرس (n-1 ، n-1) حيث n هو عرض المصفوفة المربعة المحددة. جميع المؤشرات على هذا القطر لها i = j.
لذا يمكننا تكرار هذا القطر في حلقة كالتالي:

1. قم بتهيئة i = 0 و j = 0.
2. تشغيل حلقة بينما أنا
3. أضف العنصر الحالي. قم بزيادة كل من i و j بمقدار 1.

الآن دعونا نرى للقطري الثانوي. فهرس العنصر الأول في الصف الأول هو i = 0 ، j = n-1. العنصر التالي هو (i + 1.j-1). العنصر الأخير بالمثل هو في (n-1,0،XNUMX).
لذا يمكننا التكرار على هذا القطر في الحلقة على النحو التالي:

1. قم بتهيئة i = 0 و j = n-1.
2. تشغيل حلقة بينما أنا = 0.
3. أضف العنصر الحالي (إذا كان لا يقع على القطر الأساسي ، أي i == j). قم بزيادة i بمقدار 1 وتقليل j بمقدار 1.

أخيرًا ، أعد المجموع بعد كلتا العمليتين.

تطبيق

برنامج C ++ لحل Matrix Diagonal Sum Leetcode

#include <bits/stdc++.h>
using namespace std;

int diagonalSum(vector<vector<int>>& mat) 
{
    int n=mat.size();

    int sum=0;
    int i=0,j=0;

    while(i<n)
    {
        sum+=mat[i][j];
        i++;
        j++;
    }

    i=0;
    j=n-1;

    while(i<n)
    {
        if(i!=j)   sum+=mat[i][j];
        i++;
        j--;
    }

    return sum;
}

int main() 
{
    vector<vector<int>> mat={
            {1,2,3},
            {4,5,6},
            {7,8,9}  
    };
   
    cout<<diagonalSum(mat)<<endl;

  return 0; 
}
25

برنامج جافا لحل Matrix Diagonal Sum Leetcode

import java.lang.*;

class Rextester
{  
    public static int diagonalSum(int[][] mat) 
    {
        int n=mat.length;
        
        int sum=0;
        int i=0,j=0;
        
        while(i<n)
        {
            sum+=mat[i][j];
            i++;
            j++;
        }
        
        i=0;
        j=n-1;
        
        while(i<n)
        {
          if(i!=j)   sum+=mat[i][j];
            
            i++;
            j--;
        }
        
        return sum;
        
    }
    
    public static void main(String args[])
    {
       int[][] mat={
            {1,2,3},
            {4,5,6},
            {7,8,9}  
        };
    
       System.out.println(diagonalSum(mat));
   
    }
}
25

تحليل التعقيد لمصفوفة قطري مجموع حل Leetcode

تعقيد الوقت

على) : هنا N هو حجم المصفوفة المربعة التي تحتوي على عناصر N ^ 2. نظرًا لأننا نجتاز فقط كلا العنصرين القطريين ، فإن تعقيد الوقت سيكون مساويًا لعدد العناصر الموجودة في الأقطار (2 * N) ، أي O (N).

تعقيد الفضاء 

يا (1): هنا يكون تعقيد الفضاء ثابتًا لأننا لا نستخدم أي ذاكرة إضافية.