រាប់លេខអវិជ្ជមាននៅក្នុងដំណោះស្រាយម៉ាទ្រីស LeetCode



LeetCode ម៉ាទ្រីស

សេចក្តីថ្លែងការណ៍បញ្ហា

នៅក្នុងបញ្ហា“ រាប់លេខអវិជ្ជមាននៅក្នុងម៉ាទ្រីសតម្រៀប” យើងត្រូវបានផ្តល់អោយ ម៉ាទ្រីស នៃជួរដេក 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} ។ ដូច្នេះចំនួនសរុបនៃលេខអវិជ្ជមានគឺ ៨ ។

វិធីសាស្រ្ត

ដើម្បីយល់ពីវិធីសាស្រ្តកាន់តែប្រសើរសូមឱ្យយើងប្រើឧទាហរណ៍ដូចគ្នាសម្រាប់ការយល់ដឹងកាន់តែប្រសើរ។ យើងនឹងឃើញម៉ាទ្រីសដែលបានផ្តល់ជាសំណុំមួយ តម្លៃវិជ្ជមាននិងអវិជ្ជមាន ហើយនឹងមិនអើពើពីទំហំរបស់វា។ ដូច្នេះម៉ាទ្រីសដែលបានផ្តល់ឱ្យត្រូវបានបម្លែងទៅជាសំណុំនៃតម្លៃវិជ្ជមាននិងអវិជ្ជមាន។

ដំណោះស្រាយ leetcode ដើម្បីរាប់លេខអវិជ្ជមាននៅក្នុងម៉ាទ្រីសតម្រៀប

ដូច្នេះយើងដឹងរួចហើយថាម៉ាទ្រីសត្រូវបានតម្រៀបតាមលំដាប់លំដោយថយចុះលំដាប់ជួរជួរក៏ដូចជាជួរឈរផងដែរយើងនឹងប្រើវាដើម្បីដោះស្រាយបញ្ហា យើងនឹងចាប់ផ្តើមជាមួយជួរទីមួយហើយនឹងចាប់ផ្តើមឆ្លងកាត់ ពីឆ្វេងទៅស្តាំ រហូតដល់យើងជួបប្រទះធាតុវិជ្ជមាន (សូមហៅវា 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 គឺជាចំនួនជួរដេកនិងចំនួនជួរឈររៀងៗខ្លួន។

ភាពស្មុគស្មាញនៃលំហ

ភាពស្មុគស្មាញចន្លោះនៃលេខកូដខាងលើគឺ ឱ (១) ពីព្រោះយើងកំពុងប្រើតែអថេរដើម្បីរក្សាទុកចម្លើយ។

ឯកសារយោង