በማትሪክስ ሌቲኮድ መፍትሔ ውስጥ ኬ በጣም ደካማ ረድፎች  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን
ስልተ ሰልፍ የሁለትዮሽ ፍለጋ ምስጠራ ቃለ መጠይቅ interviewprep ሊት ኮድ LeetCodeSolutions

የችግር እሴት  

በችግሩ ውስጥ “K K በጣም ደካማው ረድፎች በማትሪክስ ውስጥ” እኛ ተሰጠን ማትሪክስ የ n ረድፎች እና ሜትር አምዶች። ማትሪክስ በ 0 ወይም 1. ተሞልቷል - የዚህ ማትሪክስ ልዩ ነገር ሁሉም ወደ እያንዳንዱ ረድፍ ወደ ግራ-ግራ እና ሁሉም ዜሮዎች ወደ ቀኝ-ቀኝ ናቸው ፡፡

የእያንዲንደ ረድፍ ጥንካሬን ሇመመሇከት ህጎች ስብስብ አለ።

  1. ብዙ ቁጥር ያላቸው ረድፎች የበለጠ ጥንካሬ አላቸው ፡፡
  2. ማሰሪያው ከተከሰተ ከዚያ በትንሽ ረድፍ ቁጥር ያለው ረድፍ አነስተኛ ጥንካሬ አለው።

ችግሩ በማትሪክስ ውስጥ በጣም ደካማ ረድፎችን ለማግኘት ይጠይቃል ፡፡

ለምሳሌ

grid = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
[2,0,3]

ማብራሪያ:

  • ዜሮ ረድፍ -> 2
  • የመጀመሪያ ረድፍ-> 4
  • ሁለተኛ ረድፍ-> 1
  • ሦስተኛው ረድፍ-> 2
  • አራተኛው ረድፍ-> 5

በዜሮ እና በአራተኛው ረድፍ መካከል አራተኛው የበለጠ ጠንካራ ነው ፡፡ ስለዚህ ረድፎቹ ከደካማ ወደ ጠንካራ የተደራጁት - 2,0,3,1,4 ፡፡

በማትሪክስ ሌትኮድ መፍትሄ ውስጥ የ “K” ደካማ ረድፎች አቀራረብ  

አቀራረቡን በተሻለ ለመረዳት አንድን ምሳሌ ለተሻለ ግንዛቤ እንጠቀም ፡፡ በእያንዳንዱ ረድፍ ውስጥ ያሉትን ቁጥር ይቁጠሩ ፡፡ ግን የተሟላውን ረድፍ በማለፍ ይህንን ስናደርግ መስመራዊ ጊዜ ይወስዳል ፡፡ ስለዚህ የጊዜን ውስብስብነት ለማሻሻል በእያንዳንዱ ረድፍ ውስጥ የመጀመሪያውን ዜሮ መረጃ ጠቋሚ ለመፈለግ የሁለትዮሽ ፍለጋን እንጠቀማለን እናም ይህ መረጃ ጠቋሚው በእያንዳንዱ ረድፍ ውስጥ ያሉት ይሆናል ፡፡

ተመልከት
ኢንቲጀር ለሮማን

በሁለት ሁኔታዎች መሠረት መደርደር እንፈልጋለን-

  1. በእያንዳንዱ ረድፍ ውስጥ የአንዶች ብዛት።
  2. የአንዶቹ ቁጥር እኩል ከሆነ ከዚያ የረድፍ ቁጥር።

ይህንን ብልሃት በመጠቀም ወደ አንድ ተለዋዋጭ መለወጥ እንችላለን ፡፡ ከመግለጫው ዓይነት ሁኔታ ጋር የሚስማማ ውጤት መፍጠር እንችላለን ፡፡

በማትሪክስ ውስጥ ለ k በጣም ደካማ ረድፎች የሌትኮድ መፍትሄጭንቅላታም መያያዣ መርፌ

 

ውጤት = ወታደሮች ቁጥር * ረድፎች + currentRowIndex

ስለዚህ ወታደሮችን / ውጤቶችን በውጤት / ረድፎች ማግኘት እና የረድፍ ኢንዴክስን በውጤት% ረድፎች ማግኘት እንችላለን ፡፡

አሁን ውጤቱን እንመድባለን እና የመነሻ k ውጤት ማውጫ መልስ ይሆናል ፡፡

አፈጻጸም

ለ ‹K› በጣም ደካማ ረድፎች በማትሪክስ ውስጥ C ++ ኮድ

#include <bits/stdc++.h>
using namespace std; 
 int numOnes( vector<int> row) {
        int lo = 0;
        int hi = row.size();
        
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (row[mid] == 1)
                lo = mid + 1;
            else
                hi = mid;
        }
        
        return lo;
    }
vector<int> kWeakestRows(vector<vector<int>>& mat, int k)  {
    int rows = mat.size();
    int cols = mat[0].size();

    int score[rows];
    int j;
    for (int i = 0; i < rows; i++) {
         j = numOnes(mat[i]);
        score[i] = j * rows + i;
    }

    sort(score,score+rows);
    vector<int>ans(k);
    for (int i = 0; i < k; i++) {
        ans[i] = score[i] % rows;
    }

    return ans;
}
int main() 
{ 
 vector<vector<int> > arr = { {1,1,0,0,0 }, 
                              { 1,1,1,1,0 }, 
                              { 1,0,0,0,0 },
                              { 1,1,0,0,0 },
                              { 1,1,1,1,1 }}; 
 int k=3;                               
 vector<int>ans=kWeakestRows(arr,k); 
 for(int i=0;i<k;i++)
 cout<<ans[i]<<" ";
 cout<<endl;
 return 0;
}
2 0 3

ለ ‹ኬ› ደካማ ረድፎች በማትሪክስ ውስጥ የጃቫ ኮድ

import java.util.*;
public class Tutorialcup {
       public static int numOnes(int[] row) {
        int lo = 0;
        int hi = row.length;
        
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (row[mid] == 1)
                lo = mid + 1;
            else
                hi = mid;
        }
        
        return lo;
    }
       public static int[] kWeakestRows(int[][] mat, int k) {
    int rows = mat.length;
    int cols = mat[0].length;

    int[] score = new int[rows];
    int j;
    for (int i = 0; i < rows; i++) {
         j = numOnes(mat[i]);
        score[i] = j * rows + i;
    }

    Arrays.sort(score);
    for (int i = 0; i < k; i++) {
        score[i] = score[i] % rows;
    }

    return Arrays.copyOfRange(score, 0, k);
}
   public static void main(String[] args) {
    int [][] arr ={      {1,1,0,0,0 }, 
                              { 1,1,1,1,0 }, 
                              { 1,0,0,0,0 },
                              { 1,1,0,0,0 },
                              { 1,1,1,1,1 }}; 
        int k=3;                               
        int[]ans=kWeakestRows(arr,k); 
        System.out.println(Arrays.toString(ans));
  }
}
2 0 3

በማትሪክስ ሌትኮድ መፍትሄ ውስጥ የ “K” በጣም ደካማ ረድፎች ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ከላይ ያለው ኮድ የጊዜ ውስብስብነት ነው ኦ (n * logm + nlogn). n * logm በእያንዳንዱ ረድፍ የአንዱን ቁጥር ለማስላት ሲሆን n * logn ደግሞ ለመደርደር ነው ፡፡ እዚህ n የረድፎች ቁጥሮች ሲሆን መ ደግሞ የአምዶች ቁጥር ነው።

ተመልከት
የተማሪዎች የስብሰባ መዝገብ I Leetcode Solution

የቦታ ውስብስብነት

ከላይ ያለው ኮድ የቦታ ውስብስብነት ነው ሆይ (n) ምክንያቱም ውጤቱን እያከማቸነው ነው ፡፡ እዚህ n በማትሪክስ ውስጥ የረድፎች ብዛት ነው።

ማጣቀሻዎች