Sıralanmış bir Matris LeetCode həllində mənfi ədədi sayın


alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions MatrisBaxılıb 34

Problem bəyanat

“Sıralanmış bir matrisdəki mənfi ədədi sayın” problemində bizə a verilir matris n sətir və m sütunun. Elementlər həm satır, həm də sütun baxımından azalan qaydada sıralanır. Matrisdəki mənfi elementlərin ümumi sayını tapmaq lazımdır.

misal

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

Explanation: Verilən matrisdəki kimi mənfi ədədlər: {-1, -1, -1, -2, -1, -1, -2, -3}. Beləliklə, mənfi rəqəmlərin ümumi sayı 8-dir.

Yanaşma

Yanaşmanı daha yaxşı başa düşmək üçün daha yaxşı başa düşmək üçün eyni nümunədən istifadə edək. Verilən matrisi bir sıra olaraq görəcəyik müsbət və mənfi dəyərlər və onun böyüklüyünə məhəl qoymayacaqdır. Beləliklə, verilən matris müsbət və mənfi dəyərlər toplusuna çevrilir.

Sıralanmış Matritsada Mənfi Nömrələri saymaq üçün lekkod həlliPin

Beləliklə, matrisin sütun müdrikliyi ilə yanaşı azalan sıra sırası ilə də sıralandığını bilirik, bu problemi həll etmək üçün istifadə edəcəyik. Birinci sıra ilə başlayacağıq və keçməyə başlayacağıq sağdan sola müsbət bir elementlə qarşılaşana qədər (gəlin çağıraq ilə). Birinci cərgədəki mənfi elementlərin ümumi sayı => m - col - 1 olacaqdır. İndi növbəti sıraya keçəcəyik. Burada elementlərin sıralanması faktından istifadə gəlir. Matritsanın [0] [col]> = matrix [1] [col] dəyəri və matrisə [1] [col] olan bütün elementlərin dəyəri ondan kiçik olduğu üçün kolun solundakı elementləri keçməyimiz lazım deyil..

İndi matris [1] [col] müsbətdirsə, onda birinci cərgədəki mənfi elementlərin ümumi sayı => m - col - 1 olacaq, başqa bir pozitiv elementlə qarşılaşana qədər sağdan sola keçməyə davam edəcəyik. Bütün satırları ziyarət edənə qədər bu addımları izləyəcəyik. Bütün sətirlərdən mənfi rəqəmlərin yekun ümumi sayı cavabımız olacaq.

Kodu

Sıralanmış bir Matrix LeetCode həllində mənfi ədədi saymaq üçün C ++ kodu

#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

Sıralanmış Matrix LeetCode həllində mənfi ədədi saymaq üçün Java kodu

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

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n + m) çünki hər sətirdən və ən pis halda bütün sütunlardan keçirik. Burada n və m sırasıyla sətir və sütun sayıdır.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki cavabı saxlamaq üçün yalnız dəyişəndən istifadə edirik.

References

Şərh yaz

Translate »