ವಿಂಗಡಿಸಲಾದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ನಕಾರಾತ್ಮಕ ಸಂಖ್ಯೆಗಳನ್ನು ಎಣಿಸಿ



ಲೀಟ್‌ಕೋಡ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ವಿಂಗಡಿಸಲಾದ ಮ್ಯಾಟ್ರಿಕ್ಸ್‌ನಲ್ಲಿ ನಕಾರಾತ್ಮಕ ಸಂಖ್ಯೆಗಳನ್ನು ಎಣಿಸಿ” ಎಂಬ ಸಮಸ್ಯೆಯಲ್ಲಿ ನಮಗೆ ನೀಡಲಾಗಿದೆ ಮ್ಯಾಟ್ರಿಕ್ಸ್ n ಸಾಲುಗಳು ಮತ್ತು ಮೀ ಕಾಲಮ್‌ಗಳ. ಸಾಲು-ಬುದ್ಧಿವಂತ ಮತ್ತು ಕಾಲಮ್-ಬುದ್ಧಿವಂತಿಕೆಯಂತೆ ಅಂಶಗಳನ್ನು ಕಡಿಮೆ ಮಾಡುವಲ್ಲಿ ವಿಂಗಡಿಸಲಾಗಿದೆ. ಮ್ಯಾಟ್ರಿಕ್ಸ್‌ನಲ್ಲಿ ನಾವು ಒಟ್ಟು negative ಣಾತ್ಮಕ ಅಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ.

ಉದಾಹರಣೆ

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 ಆಗಿದೆ.

ಅಪ್ರೋಚ್

ವಿಧಾನವನ್ನು ಚೆನ್ನಾಗಿ ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು ಉತ್ತಮ ತಿಳುವಳಿಕೆಗಾಗಿ ಅದೇ ಉದಾಹರಣೆಯನ್ನು ಬಳಸೋಣ. ಕೊಟ್ಟಿರುವ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ನಾವು ಒಂದು ಗುಂಪಾಗಿ ನೋಡುತ್ತೇವೆ ಧನಾತ್ಮಕ ಮತ್ತು negative ಣಾತ್ಮಕ ಮೌಲ್ಯಗಳು ಮತ್ತು ಅದರ ಪ್ರಮಾಣವನ್ನು ನಿರ್ಲಕ್ಷಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ ಕೊಟ್ಟಿರುವ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಧನಾತ್ಮಕ ಮತ್ತು negative ಣಾತ್ಮಕ ಮೌಲ್ಯಗಳ ಗುಂಪಾಗಿ ಪರಿವರ್ತಿಸಲಾಗುತ್ತದೆ.

ವಿಂಗಡಿಸಲಾದ ಮ್ಯಾಟ್ರಿಕ್ಸ್‌ನಲ್ಲಿ ನಕಾರಾತ್ಮಕ ಸಂಖ್ಯೆಗಳನ್ನು ಎಣಿಸಲು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಆದ್ದರಿಂದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಸಾಲು-ಬುದ್ಧಿವಂತ ಮತ್ತು ಕಾಲಮ್-ಬುದ್ಧಿವಂತಿಕೆಯಂತೆ ವಿಂಗಡಿಸಲಾಗಿದೆ ಎಂದು ನಾವು ಈಗಾಗಲೇ ತಿಳಿದಿದ್ದೇವೆ, ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ನಾವು ಅದನ್ನು ಬಳಸುತ್ತೇವೆ. ನಾವು ಮೊದಲ ಸಾಲಿನಿಂದ ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ ಮತ್ತು ಅದರಿಂದ ಸಂಚರಿಸಲು ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ ಬಲದಿಂದ ಎಡಕ್ಕೆ ನಾವು ಸಕಾರಾತ್ಮಕ ಅಂಶವನ್ನು ಎದುರಿಸುವವರೆಗೆ (ಅದನ್ನು ಕರೆಯೋಣ ಕಾಲರ್). ಮೊದಲ ಸಾಲಿನಲ್ಲಿನ ಒಟ್ಟು negative ಣಾತ್ಮಕ ಅಂಶಗಳ ಸಂಖ್ಯೆ => m - col - 1. ಆಗಿರುತ್ತದೆ. ಈಗ ನಾವು ಮುಂದಿನ ಸಾಲಿಗೆ ಹೋಗುತ್ತೇವೆ. ಅಂಶಗಳನ್ನು ವಿಂಗಡಿಸಲಾಗಿದೆ ಎಂಬ ಅಂಶದ ಬಳಕೆ ಇಲ್ಲಿದೆ. ನಾವು ಕೋಲ್ನ ಎಡಭಾಗದಲ್ಲಿರುವ ಅಂಶಗಳನ್ನು ಹಾದುಹೋಗುವ ಅಗತ್ಯವಿಲ್ಲ ಏಕೆಂದರೆ ಮ್ಯಾಟ್ರಿಕ್ಸ್ [0] [ಕೋಲ್]> = ಮ್ಯಾಟ್ರಿಕ್ಸ್ [1] [ಕೋಲ್] ಮತ್ತು ಮ್ಯಾಟ್ರಿಕ್ಸ್ [1] [ಕೋಲ್] ಗೆ ಬಲವಿರುವ ಎಲ್ಲಾ ಅಂಶಗಳು ಅದಕ್ಕಿಂತ ಚಿಕ್ಕದಾಗಿದೆ.

ಈಗ ಮ್ಯಾಟ್ರಿಕ್ಸ್ [1] [ಕೋಲ್] ಸಕಾರಾತ್ಮಕವಾಗಿದ್ದರೆ ಮೊದಲ ಸಾಲಿನಲ್ಲಿರುವ ಒಟ್ಟು negative ಣಾತ್ಮಕ ಅಂಶಗಳ ಸಂಖ್ಯೆ => ಮೀ - ಕೋಲ್ - 1 ಆಗಿರುತ್ತದೆ, ಇಲ್ಲದಿದ್ದರೆ ನಾವು ಧನಾತ್ಮಕ ಅಂಶವನ್ನು ಎದುರಿಸುವವರೆಗೆ ಬಲದಿಂದ ಎಡಕ್ಕೆ ಚಲಿಸುತ್ತೇವೆ. ನಾವು ಎಲ್ಲಾ ಸಾಲುಗಳನ್ನು ಭೇಟಿ ಮಾಡುವವರೆಗೆ ನಾವು ಈ ಹಂತಗಳನ್ನು ಅನುಸರಿಸುತ್ತೇವೆ. ಎಲ್ಲಾ ಸಾಲುಗಳಿಂದ negative ಣಾತ್ಮಕ ಸಂಖ್ಯೆಗಳ ಅಂತಿಮ ಒಟ್ಟು ಎಣಿಕೆ ನಮ್ಮ ಉತ್ತರವಾಗಿರುತ್ತದೆ.

ಕೋಡ್

ವಿಂಗಡಿಸಲಾದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಕೌಂಟ್ ನೆಗೆಟಿವ್ ಸಂಖ್ಯೆಗಳಿಗಾಗಿ ಸಿ ++ ಕೋಡ್

#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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯದ ಸಂಕೀರ್ಣತೆ

ಮೇಲಿನ ಕೋಡ್‌ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ ಒ (ಎನ್ + ಮೀ) ಏಕೆಂದರೆ ನಾವು ಪ್ರತಿ ಸಾಲಿನಲ್ಲಿ ಹಾದುಹೋಗುತ್ತಿದ್ದೇವೆ ಮತ್ತು ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಎಲ್ಲಾ ಕಾಲಮ್‌ಗಳು. ಇಲ್ಲಿ n ಮತ್ತು m ಗಳು ಕ್ರಮವಾಗಿ ಸಾಲುಗಳ ಸಂಖ್ಯೆಗಳು ಮತ್ತು ಕಾಲಮ್‌ಗಳ ಸಂಖ್ಯೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಮೇಲಿನ ಕೋಡ್‌ನ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ ಒ (1) ಏಕೆಂದರೆ ನಾವು ಉತ್ತರವನ್ನು ಸಂಗ್ರಹಿಸಲು ವೇರಿಯೇಬಲ್ ಅನ್ನು ಮಾತ್ರ ಬಳಸುತ್ತಿದ್ದೇವೆ.

ಉಲ್ಲೇಖಗಳು