වර්ග කළ අනුකෘති ලීට්කෝඩ් විසඳුමක සෘණ අංක ගණන් කරන්න



ලීට්කෝඩ් නියමයන්

ගැටළු ප්රකාශය

“වර්ග කළ අනුකෘතියක Neg ණ සංඛ්‍යා ගණනය කරන්න” යන ගැටලුවේදී අපට ලබා දී ඇත්තේ a අනුකෘතියයි පේළි n සහ m තීරු. මූලද්‍රව්‍ය පේළි අනුව සහ තීරු අනුව අනුපිළිවෙලින් අඩු වේ. න්‍යාසයේ ඇති negative ණාත්මක මූලද්‍රව්‍ය ගණන අපට සොයාගත යුතුය.

උදාහරණයක්

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

පැහැදිලි කිරීම: දී ඇති අනුකෘතියේ මෙන් negative ණ සංඛ්‍යා: {-1, -1, -1, -2, -1, -1, -2, -3}. එබැවින් negative ණ සංඛ්‍යා වල මුළු ගණන 8 කි.

ප්රවේශය

ප්‍රවේශය වඩා හොඳින් අවබෝධ කර ගැනීම සඳහා වඩා හොඳ අවබෝධයක් සඳහා එකම උදාහරණය භාවිතා කරමු. දී ඇති අනුකෘතිය සමූහයක් ලෙස අපි දකිමු ධනාත්මක සහ negative ණ අගයන් සහ එහි විශාලත්වය නොසලකා හරිනු ඇත. එබැවින් දී ඇති අනුකෘතිය ධනාත්මක හා negative ණ අගයන් සමූහයක් බවට පරිවර්තනය වේ.

වර්ග කළ අනුකෘතියක Neg ණ සංඛ්‍යා ගණනය කිරීම සඳහා ලීට්කෝඩ් විසඳුම

එබැවින් අනුපිළිවෙල පේළි අනුව සහ තීරු අනුව අඩු වන බව අපි දැනටමත් දනිමු, මෙම ගැටළුව විසඳීම සඳහා අපි එය භාවිතා කරමු. අපි පළමු පේළියෙන් ආරම්භ කර එතැනින් ගමන් ආරම්භ කරමු දකුණේ සිට වමට අපට ධනාත්මක අංගයක් හමු වන තුරු (අපි එය හඳුන්වමු කොල්). පළමු පේළියේ ඇති negative ණාත්මක මූලද්‍රව්‍ය ගණන => m - col - 1 වනු ඇත. දැන් අපි ඊළඟ පේළියට පනින්නෙමු. මූලද්රව්ය වර්ග කර ඇති බව භාවිතා කිරීම මෙහි පැමිණේ. න්‍යාසයේ [0] [col]> = න්‍යාසය [1] [col] සහ න්‍යාසයට දකුණට ඇති සියලුම මූලද්‍රව්‍ය [1] [col] ට වඩා කුඩා බැවින් අපට කොලෙහි වම්පස ඇති මූලද්‍රව්‍ය ගමන් කළ යුතු නොවේ..

දැන් අනුකෘතිය [1] [col] ධනාත්මක නම් පළමු පේළියේ ඇති negative ණාත්මක මූලද්‍රව්‍ය ගණන => m - col - 1 වනු ඇත. එසේ නොමැතිනම් ධනාත්මක මූලද්‍රව්‍යයක් හමු වන තෙක් අපි දකුණේ සිට වමට ගමන් කරමු. සියලුම පේළි නැරඹීමට යන තෙක් අපි මෙම පියවර අනුගමනය කරන්නෙමු. සියලු පේළි වලින් ලැබෙන negative ණ සංඛ්‍යා වල අවසාන එකතුව අපගේ පිළිතුර වේ.

කේතය

වර්ග කළ අනුකෘති ලීට්කෝඩ් විසඳුමක සෘණ සංඛ්‍යා ගණනය කිරීම සඳහා සී ++ කේතය

#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

වර්ග කළ අනුකෘති ලීට්කෝඩ් විසඳුමක සෘණ අංක ගණනය කිරීම සඳහා ජාවා කේතය

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) මොකද අපි උත්තරය ගබඩා කරන්න විචල්‍යයක් විතරයි පාවිච්චි කරන්නේ.

ආශ්රිත