क्रमवारी लावलेल्या मॅट्रिक्स लीटकोड सोल्यूशनमध्ये नकारात्मक संख्या मोजा



लेटकोड मॅट्रिक्स

समस्या विधान

“एका क्रमवारी लावलेल्या मॅट्रिक्समध्ये नकारात्मक संख्या मोजा” या समस्येमध्ये आम्हाला अ मॅट्रिक्स एन पंक्ती आणि एम स्तंभ. घटक पंक्तीनिहाय आणि स्तंभनिहाय दोन्ही क्रमानुसार क्रमवारीत लावले जातात. आम्हाला मॅट्रिक्समध्ये एकूण नकारात्मक घटकांची संख्या शोधण्याची आवश्यकता आहे.

उदाहरण

grid = [[8,3,2,-1],[4,2,1,-1],[3,1,-1,-2],[-1,-1,-2,-3]]
8

स्पष्टीकरण: दिलेल्या मॅट्रिक्स नकारात्मक संख्येप्रमाणे: {-1, -1, -1, -2, -1, -1, -2, -3}. तर negativeणात्मक संख्यांची एकूण गणना 8 आहे.

दृष्टीकोन

दृष्टिकोन अधिक चांगल्या प्रकारे समजण्यासाठी अधिक चांगले समजण्यासाठी आपण हेच उदाहरण वापरू. दिलेल्या मेट्रिक्सचा सेट म्हणून पाहू सकारात्मक आणि नकारात्मक मूल्ये आणि त्याच्या विशालतेकडे दुर्लक्ष करेल. तर दिलेली मॅट्रिक्स सकारात्मक आणि नकारात्मक मूल्यांच्या संचामध्ये रूपांतरित झाली.

क्रमवारी लावलेल्या मॅट्रिक्समधील नकारात्मक संख्या मोजण्यासाठी लीटकोड सोल्यूशन

म्हणूनच आम्हाला हे आधीच माहित आहे की मॅट्रिक्स क्रमवारीत घटते क्रमानुसार तसेच स्तंभनिहाय क्रमवारीत आहे, आम्ही या समस्येचे निराकरण करण्यासाठी त्याचा वापर करू. आम्ही पहिल्या पंक्तीपासून प्रारंभ करू आणि येथून मार्गक्रमण करू उजवीकडून डावीकडे जोपर्यंत आपल्याला सकारात्मक घटक आढळत नाही (चला याला कॉल करूया कॉलर). पहिल्या ओळीतील नकारात्मक घटकांची एकूण संख्या => मी - कोल - १ असेल. आता आपण पुढच्या ओळीवर जाऊ. येथे घटकांची क्रमवारी लावल्या जाणार्‍या वस्तुस्थितीचा वापर केला जातो. आम्हाला कोलच्या डावीकडे असलेल्या आडव्या घटकांची आवश्यकता नाही कारण मॅट्रिक्स [0] [कोल]> = मॅट्रिक्स [1] [कोल] आणि मॅट्रिक्स [1] [कॉल] च्या सर्व घटकांचे मूल्य त्यापेक्षा लहान आहे..

आता जर मॅट्रिक्स [1] [कॉल] सकारात्मक असेल तर पहिल्या पंक्तीतील नकारात्मक घटकांची एकूण संख्या => मी - कोल - 1 असेल अन्यथा आम्ही जोपर्यंत एखादा सकारात्मक घटक येत नाही तोपर्यंत आम्ही उजवीकडून डावीकडे सरकतो. आम्ही सर्व पंक्तींना भेट देईपर्यंत या चरणांचे अनुसरण करू. सर्व पंक्तींमधील नकारात्मक संख्यांची अंतिम एकूण गणना आपले उत्तर असेल.

कोड

क्रमवारी लावलेल्या मॅट्रिक्स लीटकोड सोल्यूशनमधील नकारात्मक संख्या मोजण्यासाठी सी ++ कोड

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

 int count(vector<vector<int>>& grid)
 {
  int n=grid.size(),m=grid[0].size(), row=0, column=m - 1,ans=0;
        while (row < n) {
            while (column >= 0 && grid[row][column] < 0) column--;
            ans += m - column - 1;
            row++;
        }
        return ans; 
 }

int main() 
{ 
 vector<vector<int> > arr = { { 8,3,2,-1 }, 
                              { 4,2,1,-1 }, 
                              { 3,1,-1,-2 },
                              { -1,-1,-2,-3 }}; 
 cout<<count(arr)<<endl; 
 return 0;
}
8

क्रमवारी लावलेल्या मॅट्रिक्स लीटकोड सोल्यूशनमध्ये नकारात्मक संख्या मोजण्यासाठी जावा कोड

public class Tutorialcup {
  public static int countNegatives(int[][] grid) {
         int n=grid.length,m=grid[0].length, row=0, column=m - 1,ans=0;
          while (row < n) {
              while (column >= 0 && grid[row][column] < 0) column--;
              ans += m - column - 1;
              row++;
          }
          return ans; 
      }
  public static void main(String[] args) {
    int [][] grid = {
              {8,3,2,-1},
              {4,2,1,-1},
              {3,1,-1,2},
              {-1,-1-2,-3}
            };
    int ans= countNegatives(grid);
    System.out.println(ans);
  }
}

 

8

गुंतागुंत विश्लेषण

वेळ गुंतागुंत

वरील कोडची वेळ जटिलता आहे ओ (एन + मी) कारण आम्ही प्रत्येक पंक्तीचा शोध घेत आहोत आणि सर्वात वाईट परिस्थितीत सर्व स्तंभ. येथे एन आणि मी अनुक्रमे पंक्ती आणि स्तंभांची संख्या आहेत.

जागेची जटिलता

वरील कोडची स्पेस कॉम्प्लेक्सिटी आहे ओ (1) कारण आम्ही उत्तर संग्रहित करण्यासाठी फक्त एक व्हेरिएबल वापरत आहोत.

संदर्भ