တစ် ဦး Sorted Matrix LeetCode ဖြေရှင်းချက်အတွက်အနုတ်လက္ခဏာနံပါတ်များကိုရေတွက်



LeetCode matrix

ပြstatementနာကြေညာချက်

“ Sorted Matrix ထဲတွင်အနှုတ်နံပါတ်များကိုရေတွက်ပါ” ပြproblemနာတွင်ကျွန်ုပ်တို့အား a matrix n အတန်းနှင့်မီတာကော်လံ၏။ Element တွေကိုအတန်းလိုက်နှင့်ကော်လံ - စာသားများကိုအစဉ်လိုက်စီစဉ်ပေးသည်။ ကျနော်တို့စုစုပေါင်းအနုတ်လက္ခဏာဒြပ်စင်များ matrix ကိုရှာရန်လိုအပ်သည်။

နမူနာ

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

ရှင်းလင်းချက်: ပေးထားသော matrix ၌ရှိသကဲ့သို့အနုတ်လက္ခဏာနံပါတ်များမှာ {-1, -1, -1, -2, -1, -1, -2, -3} ။ ဒါဆိုအနှုတ်ဂဏန်းတွေရဲ့စုစုပေါင်းက ၈ ။

ချဉ်းကပ်နည်း

ချဉ်းကပ်မှုကိုပိုမိုနားလည်ရန်ကျွန်ုပ်တို့ကိုပိုမိုနားလည်ရန်အတွက်တူညီသောဥပမာကိုသုံးပါ။ ကျနော်တို့ပေးထားသော matrix ကိုအစုတခုအဖြစ်မြင်လိမ့်မည် အပြုသဘောနှင့်အနှုတ်တန်ဖိုးများ နှင့်၎င်း၏ပြင်းအားလျစ်လျူရှုပါလိမ့်မယ်။ ဒီတော့ပေးထားတဲ့ matrix ကိုအပေါင်းနှင့်အနှုတ်တန်ဖိုးများအဖြစ်ပြောင်းလိုက်တယ်။

တစ် ဦး Sorted Matrix အတွက်အနှုတ်လက္ခဏာနံပါတ်များကိုရေတွက်ဖို့ leetcode ဖြေရှင်းချက်

ဒီတော့ဒီ matrix ကိုအစဉ်အတန်းလိုက်အစဉ်လိုက်အစဉ်လိုက်စီရင်လိုက်မယ်ဆိုတာကိုငါတို့သိပြီးပြီ။ ဒီပြproblemနာကိုဖြေရှင်းဖို့ငါတို့သုံးမယ်။ ကျနော်တို့ပထမ ဦး ဆုံးအတန်းနှင့်အတူစတင်ပါလိမ့်မည်နှင့်မှဖြတ်သန်းစတင်ပါလိမ့်မယ် ဘယ်ဘက်ညာ ကျွန်ုပ်တို့သည်အပြုသဘောဆောင်သောဒြပ်စင်တစ်ခုကိုမတွေ့မချင်း (၎င်းကိုခေါ်ကြစို့) လည်ပတ်) ။ ပထမအတန်းရှိအနုတ်လက္ခဏာစုစုပေါင်းသည် => m - col - ၁ ဖြစ်လိမ့်မည်။ ဤတွင်ဒြပ်စင်များကိုအမျိုးအစားခွဲထားသောအချက်ကိုအသုံးပြုသည်။ Col ၏ဘယ်ဘက်တွင်ရှိသော element များကိုဖြတ်သန်းရန်မလိုအပ်ပါ။ အဘယ့်ကြောင့်ဆိုသော် matrix ၏တန်ဖိုးသည်တန်ဖိုး [0] [col]> = matrix [1] [col] နှင့် matrix ၏ညာဘက်ရှိ element အားလုံးသည် ၁ ထက်သာသည်။.

အကယ်၍ matrix [1] [col] သည်အပြုသဘောဖြစ်ပါကပထမတန်းတန်းရှိအနုတ်လက္ခဏာစုစုပေါင်းသည် => m - col - 1 ဖြစ်လျှင်၊ ကျွန်ုပ်တို့သည်အပြုသဘောပါသောဒြပ်စင်တစ်ခုကိုတွေ့သည်အထိညာမှဘယ်သို့ရွေ့သွားမည်ဖြစ်သည်။ အတန်းတွေအားလုံးကိုမရောက်မချင်းဒီအဆင့်တွေကိုကျွန်တော်တို့လိုက်သွားမယ်။ အတန်းအားလုံးမှအနှုတ်စုစုပေါင်း၏နောက်ဆုံးစုစုပေါင်းအရေအတွက်သည်ကျွန်ုပ်တို့၏အဖြေဖြစ်သည်။

ကုဒ်

Count Negative နံပါတ်များအတွက် C ++ code ကို Sorted Matrix 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

Count Negative နံပါတ်များအတွက် Java Code ကို Sorted Matrix LeetCode Solution တွင်လုပ်သည်

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အထက်ပါကုဒ်၏အချိန်ရှုပ်ထွေးသည် အို (n + m) ဘာလို့လဲဆိုတော့ငါတို့ကအတန်းတစ်ခုစီကိုဖြတ်ပြီး၊ ဤတွင် n နှင့် m သည်အတန်းနှင့်နံပါတ်များအသီးသီးဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အပေါ်ကကုဒ်ရဲ့ရှုပ်ထွေးမှုက အို (၁) ဘာလို့လဲဆိုတော့ငါတို့ကအဖြေကိုသိမ်းဖို့ variable တစ်ခုပဲသုံးတယ်။

ကိုးကား