Падлік адмоўных лікаў у адсартаваным матрычным рашэнні LeetCode



LeetCode матрыца

Пастаноўка праблемы

У задачы «Падлік адмоўных лікаў у адсартаванай матрыцы» нам дадзена матрыца з 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 - col - 1. Цяпер мы пяройдзем да наступнага радка. Тут выкарыстоўваецца той факт, што элементы сартуюцца. Нам не трэба перамяшчаць элементы, якія знаходзяцца злева ад col, таму што значэнне матрыцы [0] [col]> = матрыца [1] [col] і ўсе элементы справа да матрыцы [1] [col] меншае за яго.

Цяпер, калі матрыца [1] [col] дадатная, тады агульная колькасць адмоўных элементаў у першым радку будзе => m - col - 1, інакш мы будзем рухацца справа налева, пакуль не сустрэнем станоўчы элемент. Мы будзем выконваць гэтыя дзеянні, пакуль не наведаем усе радкі. Канчатковы агульны лік адмоўных лікаў з усіх радкоў будзе нашым адказам.

код

Код C ++ для падліку адмоўных лікаў у адсартаваным рашэнні LeetCode Matrix

#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) таму што мы выкарыстоўваем толькі зменную для захоўвання адказу.

Спасылкі