ਇੱਕ ਕ੍ਰਮਬੱਧ ਮੈਟਰਿਕਸ ਲੀਟਕੋਡ ਹੱਲ ਵਿੱਚ ਨਕਾਰਾਤਮਕ ਨੰਬਰ ਗਿਣੋ



LeetCode ਮੈਟਰਿਕਸ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

“ਇੱਕ ਕ੍ਰਮਬੱਧ ਮੈਟ੍ਰਿਕਸ ਵਿੱਚ ਨਕਾਰਾਤਮਕ ਨੰਬਰ ਗਿਣੋ” ਸਮੱਸਿਆ ਵਿੱਚ ਸਾਨੂੰ ਇੱਕ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ ਮੈਟਰਿਕਸ n ਕਤਾਰਾਂ ਅਤੇ m ਕਾਲਮਾਂ ਦੀ. ਐਲੀਮੈਂਟਸ ਘੱਟਦੇ ਕ੍ਰਮ ਵਿੱਚ ਕ੍ਰਮਵਾਰ ਅਤੇ ਕਾਲਮ-ਅਨੁਸਾਰ ਦੋਵੇਂ ਕ੍ਰਮਬੱਧ ਕੀਤੇ ਜਾਂਦੇ ਹਨ. ਸਾਨੂੰ ਮੈਟ੍ਰਿਕਸ ਵਿੱਚ ਨਕਾਰਾਤਮਕ ਤੱਤਾਂ ਦੀ ਕੁੱਲ ਗਿਣਤੀ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਉਦਾਹਰਨ

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}. ਇਸ ਲਈ ਨਕਾਰਾਤਮਕ ਸੰਖਿਆਵਾਂ ਦੀ ਕੁੱਲ ਗਿਣਤੀ 8 ਹੈ.

ਪਹੁੰਚ

ਪਹੁੰਚ ਨੂੰ ਬਿਹਤਰ ਤਰੀਕੇ ਨਾਲ ਸਮਝਣ ਲਈ ਆਓ ਅਸੀਂ ਚੰਗੀ ਮਿਸਾਲ ਲਈ ਉਸੀ ਉਦਾਹਰਣ ਦੀ ਵਰਤੋਂ ਕਰੀਏ. ਅਸੀਂ ਦਿੱਤੇ ਮੈਟ੍ਰਿਕਸ ਨੂੰ ਸੈਟ ਦੇ ਰੂਪ ਵਿੱਚ ਵੇਖਾਂਗੇ ਸਕਾਰਾਤਮਕ ਅਤੇ ਨਕਾਰਾਤਮਕ ਮੁੱਲ ਅਤੇ ਇਸ ਦੇ ਮਾਪ ਨੂੰ ਨਜ਼ਰਅੰਦਾਜ਼ ਕਰੇਗਾ. ਸੋ ਦਿੱਤੇ ਗਏ ਮੈਟ੍ਰਿਕਸ ਸਕਾਰਾਤਮਕ ਅਤੇ ਨਕਾਰਾਤਮਕ ਮੁੱਲਾਂ ਦੇ ਸਮੂਹ ਵਿੱਚ ਬਦਲ ਗਏ.

ਕ੍ਰਮਬੱਧ ਮੈਟ੍ਰਿਕਸ ਵਿੱਚ ਰਿਣਾਤਮਕ ਨੰਬਰ ਗਿਣਨ ਲਈ ਲੀਟਕੋਡ ਹੱਲ

ਇਸ ਲਈ ਅਸੀਂ ਪਹਿਲਾਂ ਹੀ ਜਾਣਦੇ ਹਾਂ ਕਿ ਮੈਟ੍ਰਿਕਸ ਕ੍ਰਮਵਾਰ ਘੱਟ ਰਹੀ ਕ੍ਰਮ-ਕ੍ਰਮ ਦੇ ਨਾਲ ਨਾਲ ਕਾਲਮ-ਵਾਈਜ ਦੇ ਅਨੁਸਾਰ ਕ੍ਰਮਬੱਧ ਹੈ, ਅਸੀਂ ਇਸ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਇਸ ਦੀ ਵਰਤੋਂ ਕਰਾਂਗੇ. ਅਸੀਂ ਪਹਿਲੀ ਕਤਾਰ ਨਾਲ ਅਰੰਭ ਕਰਾਂਗੇ ਅਤੇ ਤੋਂ ਲੰਘਣਾ ਸ਼ੁਰੂ ਕਰਾਂਗੇ ਸੱਜੇ ਤੋਂ ਖੱਬੇ ਜਦ ਤੱਕ ਅਸੀਂ ਸਕਾਰਾਤਮਕ ਤੱਤ ਦਾ ਸਾਹਮਣਾ ਨਹੀਂ ਕਰਦੇ (ਆਓ ਇਸਨੂੰ ਕਾਲ ਕਰੀਏ) ਕੋਲ). ਪਹਿਲੀ ਕਤਾਰ ਵਿਚ ਨਕਾਰਾਤਮਕ ਤੱਤਾਂ ਦੀ ਕੁੱਲ ਸੰਖਿਆ => ਮੀ - ਕੋਲ - 1. ਹੋਵੇਗੀ. ਹੁਣ ਅਸੀਂ ਅਗਲੀ ਕਤਾਰ ਵਿਚ ਜਾਵਾਂਗੇ. ਇੱਥੇ ਇਸ ਤੱਥ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਜਾਂਦੀ ਹੈ ਕਿ ਤੱਤ ਕ੍ਰਮਬੱਧ ਕੀਤੇ ਜਾਂਦੇ ਹਨ. ਸਾਨੂੰ ਕੌਲ ਦੇ ਖੱਬੇ ਪਾਸਿਓਂ ਲੰਘਣ ਵਾਲੇ ਤੱਤ ਦੀ ਲੋੜ ਨਹੀਂ ਹੈ ਕਿਉਂਕਿ ਮੈਟ੍ਰਿਕਸ [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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ

ਉਪਰੋਕਤ ਕੋਡ ਦੀ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਹੈ ਓ (ਐਨ + ਐਮ) ਕਿਉਂਕਿ ਅਸੀਂ ਹਰੇਕ ਕਤਾਰ ਨੂੰ ਪਾਰ ਕਰ ਰਹੇ ਹਾਂ ਅਤੇ ਸਭ ਤੋਂ ਬੁਰੀ ਸਥਿਤੀ ਵਿਚ. ਇੱਥੇ n ਅਤੇ m ਕ੍ਰਮਵਾਰ ਕਤਾਰਾਂ ਅਤੇ ਕਾਲਮਾਂ ਦੀ ਸੰਖਿਆ ਹਨ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਉਪਰੋਕਤ ਕੋਡ ਦੀ ਸਪੇਸ ਗੁੰਝਲਤਾ ਹੈ ਓ (1) ਕਿਉਂਕਿ ਅਸੀਂ ਜਵਾਬ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਸਿਰਫ ਇੱਕ ਪਰਿਵਰਤਨ ਦੀ ਵਰਤੋਂ ਕਰ ਰਹੇ ਹਾਂ.

ਹਵਾਲੇ