Брои негативни броеви во подредено решение LeetCode на матрицата



LeetCode Матрица

Проблем изјава

Во проблемот „Брои негативни броеви во подредена матрица“ ни е дадена a матрица од 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.

Пристап

За подобро разбирање на пристапот, дозволете ни да го користиме истиот пример за подобро разбирање. Дадената матрица ќе ја видиме како збир од позитивни и негативни вредности и ќе ја игнорира нејзината големина. Значи, дадената матрица се претвора во збир на позитивни и негативни вредности.

решение за лек код за броење негативни броеви во подредена матрица

Значи, веќе знаеме дека матрицата е подредена во редослед на опаѓање, како и колона, ќе ја искористиме за да го решиме овој проблем. Е започнеме со првиот ред и ќе започнеме да траверзираме од десно од лево додека не наидеме на позитивен елемент (ајде да го наречеме Депресија) Вкупниот број на негативни елементи во првиот ред ќе биде => m - колона - 1. Сега ќе скокнеме во следниот ред. Тука доаѓа употребата на фактот дека елементите се подредени. Не треба да поминуваме низ елементи што се лево од колоната затоа што вредноста на матрицата [0] [коло]> = матрица [1] [коло] и сите елементи веднаш до матрицата [1] [коло] е помала од неа.

Ако матрицата [1] [коло] е позитивна, тогаш вкупниот број на негативни елементи во првиот ред ќе биде => m - коло - уште 1, ние ќе продолжиме да траверзираме од десно кон лево, сè додека не наидеме на позитивен елемент. Willе ги следиме овие чекори додека не ги посетиме сите редови. Конечниот вкупен број на негативни броеви од сите редови ќе биде нашиот одговор.

Код

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

Анализа на сложеност

Временска сложеност

Временската сложеност на горенаведениот код е O (n + m) затоа што го прелистуваме секој ред и во најлош случај сите колони. Тука n и m се броевите на редовите и бројот на колони, соодветно.

Комплексноста на просторот

Комплексноста на просторот на горенаведениот код е О (1) затоа што користиме само променлива за складирање на одговор.

Референци