LeetCode чечими боюнча иреттелген матрицадагы терс сандарды эсептөө



LeetCode Matrix

Көйгөйдү айтуу

“Терс сандарды иргелип алынган матрицада саноо” маселесинде бизге а Булакта n катарлардын жана m мамылардын. Элементтер катар боюнча жана мамыча боюнча төмөндөө тартибинде иргелет. Матрицадагы терс элементтердин жалпы санын табышыбыз керек.

мисал

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

Explanation: Берилген матрицадагыдай терс сандар: {-1, -1, -1, -2, -1, -1, -2, -3}. Ошентип, терс сандардын жалпы саны 8 болот.

жакындоо

Бул ыкманы жакшыраак түшүнүү үчүн, жакшыраак түшүнүү үчүн ушул эле мисалды келтирели. Берилген матрицаны жыйындысы катары көрөбүз оң жана терс баалуулуктар жана анын чоңдугуна көңүл бурбай калат. Ошентип, берилген матрица оң жана терс маанилердин жыйындысына айландырылат.

Сорттолгон матрицадагы терс сандарды саноо үчүн leetcode чечими

Демек, буга чейин матрица катарлар катарында, ошондой эле мамыча тилкесинде төмөндөө иретинде иреттелгенин билгендиктен, аны ушул көйгөйдү чечүү үчүн колдонобуз. Биз биринчи катардан баштап, андан өтүп баштайбыз оңдон солго оң элементке жолукканга чейин (келгиле аны чакыралы) жака). Биринчи катардагы терс элементтердин жалпы саны => m - col - 1. болот, эми кийинки сапка секиребиз. Бул жерде элементтердин иргелип алынгандыгы колдонулат. Матрицанын мааниси [0] [col]> = matrix [1] [col] жана матрицага [1] [col] туура келген бардык элементтердин мааниси андан кичине болгондуктан, бизден col сол жагында жайгашкан элементтер өтпөйт..

Эми [1] [col] матрицасы оң болсо, анда биринчи катардагы терс элементтердин жалпы саны => m - col - 1 болот, башкача айтканда оң элемент менен жолукканга чейин оңдон солго карай жүрө беребиз. Бардык катарларды көрмөйүнчө, ушул кадамдарды аткарабыз. Бардык саптардагы терс сандардын акыркы жалпы саны биздин жооп болот.

коду

Сорттолгон матрицадагы терс сандарды эсептөө үчүн C ++ коду LeetCode Solution

#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 - тиешелүүлүгүнө жараша катарлардын жана мамылардын саны.

Космостун татаалдыгы

Жогорудагы коддун мейкиндик татаалдыгы O (1) анткени биз жоопту сактоо үчүн өзгөрмө гана колдонобуз.

шилтемелер