म्याट्रिक्स डायग्नल सम Leetcode समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब
एरे म्याट्रिक्स

समस्या वक्तव्य

म्याट्रिक्स डायग्नल सम समस्यामा वर्ग म्याट्रिक्स पूर्णाgers्क दिइएको छ। हामीले यसको विकर्णमा उपस्थित सबै तत्वहरूको योग गणना गर्नु पर्छ अर्थात् प्राथमिक विकर्णमा तत्त्वका साथै माध्यमिक विकर्ण। प्रत्येक तत्व एक पटक मात्र गणना गर्नु पर्छ।

उदाहरणका

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

व्याख्या:

विकर्ण योग: १ + + + + + + + = = २।
ध्यान दिनुहोस् कि एलिमेन्ट मट [१] [१] = only एक पटक मात्र गणना गरिन्छ

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 समाधान

दिइएको वर्ग म्याट्रिक्समा हामीले केवल विकर्ण तत्त्वहरू थप्नु पर्छ र त्यसको योग फर्काउनु पर्छ।
हेरौं विकर्ण तत्वहरूको लागि म्याट्रिक्समा सूचका pattern्क के हुन्छ। पहिले यदि हामी प्राथमिक विकर्णमा हेर्छौं भने, यसको पहिलो तत्व अनुक्रमणिका i = 0, j = 0 मा छ र अर्को तत्व (i + 1, j + 1) मा छ। त्यस्तै गरी अन्तिम तत्व अनुक्रमणिका (n-1, n-1) मा हुनेछ जहाँ n दिइएको वर्ग म्याट्रिक्सको चौडाई हो। यस विकर्णमा सबै सूचकांकहरू i = j हुन्।
त्यसो भए हामी लुगमा यो विकर्णमा पुनरावृत्ति गर्न सक्दछौं:

१. सुरु i = ० र j = ०।
२. एउटा लुप चलाउनुहोला
The. वर्तमान तत्व थप्नुहोस्। १ र १ दुबै बढाउँछु।

अब गौण विकर्णको लागि हेरौं पहिलो प row्क्तिमा पहिलो तत्वको अनुक्रमणिका i = 0, j = n-1 हो। अर्को तत्त्व (i + 1.j-1) मा छ। त्यस्तै गरी अन्तिम तत्व (n-1,0) मा छ।
त्यसैले हामी लुगमा यो विकर्ण मा पुनरावृत्ति गर्न सक्छौं:

१. सुरु i = ० र j = n-१।
२. एउटा लुप चलाउनुहोला = ०
The. हालको तत्व थप्नुहोस् (यदि यो प्राथमिक विकर्णमा छैन भने, i i == j)। १ लाई बढाउँदै i र १ लाई घटाउँछ।

अपरेशन पछि दुबै रकम फिर्ता गर्नुहोस्।

कार्यान्वयन

C ++ म्याट्रिक्स डायग्नल 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

जावा कार्यक्रम मैट्रिक्स विकर्ण 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

म्याट्रिक्स विकर्ण Sum Leetcode समाधानको लागि जटिलता विश्लेषण

समय जटिलता

O (N): यहाँ N वर्गमान म्याट्रिक्सको साइज हो N ^ 2 एलिमेन्टहरू छन्। हामी दुबै विकर्ण तत्वहरूमा मात्र पार गर्दै छौं, समय जटिलता विकर्ण (२ * N) मा उपस्थित तत्वहरूको संख्या बराबर हुनेछ, अर्थात् O (N)।

ठाउँ जटिलता 

O (१): यहाँ अन्तरिक्ष जटिलता स्थिर छ किनकि हामीले कुनै थप मेमोरी प्रयोग गरिरहेका छैनौं।