మ్యాట్రిక్స్ లీట్‌కోడ్ సొల్యూషన్‌లో కె బలహీనమైన వరుసలు


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్
అర్రే బైనరీ శోధన

సమస్యల నివేదిక

సమస్యలో ”మాతృకలోని కె బలహీనమైన వరుసలు” మాకు ఇవ్వబడ్డాయి a మాత్రిక n వరుసలు మరియు m నిలువు వరుసలు. మాతృక 0 లేదా 1 తో నిండి ఉంటుంది. ఈ మాతృక యొక్క ప్రత్యేకత ఏమిటంటే, ప్రతి వరుస యొక్క ఎడమ వైపు వైపు మరియు అన్ని సున్నాలు కుడి వైపు వైపు ఉంటాయి.

ప్రతి అడ్డు వరుస యొక్క బలాన్ని కొలవడానికి నియమాల సమితి ఉన్నాయి.

  1. ఎక్కువ సంఖ్యలో ఉన్న అడ్డు వరుసకు ఎక్కువ బలం ఉంటుంది.
  2. టై సంభవించినట్లయితే, చిన్న వరుస సంఖ్యతో అడ్డు వరుస తక్కువ బలాన్ని కలిగి ఉంటుంది.

మాతృకలో k బలహీనమైన అడ్డు వరుసలను కనుగొనమని సమస్య అడుగుతుంది.

ఉదాహరణ

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.

మ్యాట్రిక్స్ లీట్‌కోడ్ సొల్యూషన్‌లో ది కె బలహీనమైన వరుసల విధానం

విధానాన్ని బాగా అర్థం చేసుకోవడానికి, మంచి అవగాహన కోసం అదే ఉదాహరణను ఉపయోగిద్దాం. ప్రతి వరుసలోని వాటి సంఖ్యను లెక్కించండి. కానీ మేము పూర్తి వరుసలో ప్రయాణించడం ద్వారా దీన్ని చేసినప్పుడు సరళ సమయం పడుతుంది. కాబట్టి సమయ సంక్లిష్టతను మెరుగుపరచడానికి మేము ప్రతి వరుసలోని మొదటి సున్నా యొక్క సూచికను కనుగొనడానికి బైనరీ శోధనను ఉపయోగిస్తాము మరియు ఆ సూచిక ప్రతి వరుసలోని వాటి సంఖ్య అవుతుంది.

మేము రెండు షరతుల ప్రకారం సార్టింగ్ చేయాలనుకుంటున్నాము:

  1. ప్రతి వరుసలో ఉన్న వారి సంఖ్య.
  2. వాటి సంఖ్య సమానంగా ఉంటే వరుస సంఖ్య.

ఈ ట్రిక్ ఉపయోగించి మనం దానిని ఒక వేరియబుల్ గా మార్చవచ్చు. వివరణ నుండి క్రమబద్ధీకరణ స్థితికి సరిపోయేలా మేము స్కోర్‌ను సృష్టించవచ్చు.

మాతృకలోని k బలహీనమైన వరుసలకు లీట్‌కోడ్ పరిష్కారం

 

స్కోరు = సైనికుల సంఖ్య * వరుసలు + ప్రస్తుత రోఇండెక్స్

కాబట్టి మేము స్కోరు / అడ్డు వరుసల ద్వారా సైనికుల సంఖ్యను పొందవచ్చు మరియు స్కోరు% వరుసల ద్వారా రోఇండెక్స్ పొందవచ్చు.

ఇప్పుడు మేము స్కోర్ను క్రమబద్ధీకరిస్తాము మరియు ప్రారంభ 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

మ్యాట్రిక్స్లో K బలహీనమైన వరుసల కోసం జావా కోడ్

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

మ్యాట్రిక్స్ లీట్‌కోడ్ సొల్యూషన్‌లో కె బలహీనమైన వరుసల సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై కోడ్ యొక్క సమయం సంక్లిష్టత O (n * logm + nlogn). n * logm అనేది ప్రతి అడ్డు వరుసలోని వాటి సంఖ్యను లెక్కించడానికి మరియు n * లాగ్న్ క్రమబద్ధీకరించడానికి. ఇక్కడ n అనేది అడ్డు వరుసల సంఖ్య మరియు m నిలువు వరుసల సంఖ్య.

స్థల సంక్లిష్టత

పై కోడ్ యొక్క స్థల సంక్లిష్టత పై) ఎందుకంటే మేము స్కోర్‌ను నిల్వ చేస్తున్నాము. ఇక్కడ n అనేది మాతృకలోని వరుసల సంఖ్య.

ప్రస్తావనలు