დაითვალეთ უარყოფითი რიცხვები დახარისხებული მატრიცის 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 ამოხსნა უარყოფითი რიცხვების დახარისხებულ მატრიცაში

ასე რომ, ჩვენ უკვე ვიცით, რომ მატრიცა დალაგებულია როგორც მწკრივში, ასევე სვეტში, ჩვენ გამოვიყენებთ მას ამ პრობლემის გადასაჭრელად. ჩვენ დავიწყებთ პირველი რიგით და დავიწყებთ ტრავერს მარჯვნიდან მარცხნივ სანამ არ დაგვხვდება პოზიტიური ელემენტი (მოდით ვუწოდოთ მას col) პირველ რიგში ნეგატიური ელემენტების მთლიანი რაოდენობა იქნება => m - col - 1. ახლა ჩვენ გადავა შემდეგ მწკრივზე. აქ ხდება იმის ფაქტის გამოყენება, რომ ელემენტები დალაგებულია. ჩვენ არ უნდა გადავკვეთოთ კოლონის მარცხნივ მდებარე ელემენტები, რადგან მატრიცა [0] [col]> = მატრიცა [1] [col] და მატრიცაზე მყოფი ყველა ელემენტი [1] [col] არის მასზე მცირე.

თუ მატრიცა [1] [col] დადებითია, მაშინ პირველი რიგის ნეგატიური ელემენტების საერთო რაოდენობა იქნება => 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

უარყოფითი რიცხვების ჯავის კოდი დალაგებული მატრიცის 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

სირთულის ანალიზი

დროის სირთულე

ზემოთ მოცემული კოდის სირთულეა O (n + მ) იმიტომ, რომ ჩვენ ვთვლით თითოეულ სტრიქონს და უარეს შემთხვევაში ყველა სვეტს. აქ n და m შესაბამისად არის სტრიქონების და სვეტების რაოდენობა.

კოსმოსური სირთულის

ზემოთ მოცემული კოდის სივრცის სირთულეა O (1) რადგან პასუხის შესანახად ვიყენებთ მხოლოდ ცვლადს.

ლიტერატურა