Հաշվեք բացասական թվերը տեսակավորված մատրիցի LeetCode լուծման մեջ



LeetCode Matrix

Խնդրի հայտարարություն

«Հաշվել բացասական թվերը դասավորված մատրիցայում» խնդրում մեզ տրվում է ա matrix n շարքերի և մ սյունների: Էլեմենտները տեսակավորվում են ըստ տողերի և սյունակների ըստ նվազման կարգի: Մենք պետք է մատրիցում գտնենք բացասական տարրերի ընդհանուր քանակը:

Օրինակ

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 է:

Մոտեցում

Մոտեցումն ավելի լավ հասկանալու համար օգտագործենք նույն օրինակն ավելի լավ հասկանալու համար: Տրված մատրիցը մենք կտեսնենք որպես մի շարք դրական և բացասական արժեքներ և անտեսելու է դրա մեծությունը: Այսպիսով, տրված մատրիցը վերափոխվում է դրական և բացասական արժեքների ամբողջության:

դասավորված մատրիցով բացասական թվերի հաշվարկի leetcode լուծում

Այսպիսով, մենք արդեն գիտենք, որ մատրիցը տեսակավորված է ըստ հերթականության, ինչպես սյունակի, այնպես էլ նվազման կարգով, մենք այն կօգտագործենք այս խնդիրը լուծելու համար: Մենք կսկսենք առաջին շարքից և կսկսենք մերթերթել աջից ձախ մինչեւ մենք չհանդիպենք դրական տարրի (եկեք անվանենք այն) հետ) Առաջին շարքում բացասական տարրերի ընդհանուր քանակը կլինի => m - col - 1. Այժմ մենք կանցնենք հաջորդ տող: Այստեղ գալիս է այն փաստի օգտագործումը, որ տարրերը տեսակավորված են: Մենք չպետք է անցնենք սյունակի ձախ կողմում գտնվող տարրերը, որովհետև [0] [col]> = մատրիցա [1] [col] և բոլոր տարրերի հենց մատրիցայի [1] [col] արժեքը դրանից փոքր է.

Եթե ​​եթե [1] [սյուն] մատրիցան դրական է, ապա առաջին շարքում բացասական տարրերի ընդհանուր քանակը կլինի => m - col - ևս 1, մենք կշարունակենք աջ ու ձախ անցնել մինչև որևէ դրական տարրի հանդիպենք: Մենք հետևելու ենք այս քայլերին, մինչ այցելենք բոլոր շարքերը: Բոլոր տողերից բացասական թվերի վերջնական ընդհանուր հաշվարկը կլինի մեր պատասխանը:

Կոդ

C ++ կոդ `Բացասական թվերի հաշվարկի համար` տեսակավորված մատրիցով LeetCode լուծույթում

#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

Java- ի կոդը `բացասական թվերի հաշվարկի համար դասավորված մատրիցով LeetCode լուծում

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

Բարդության վերլուծություն

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (n + մ) քանի որ մենք անցնում ենք յուրաքանչյուր շարքը և վատագույն դեպքում բոլոր սյունակները: Այստեղ n և m համապատասխանաբար տողերի և սյունների քանակն են:

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է Ո (1) քանի որ մենք պատասխանը պահելու համար օգտագործում ենք միայն փոփոխական:

Սայլակ