මැට්රික්ස් ලීට්කෝඩ් විසඳුමක කේ දුර්වලම පේළි


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන්
අරා ද්විමය සෙවීම

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

“න්‍යාසයේ කේ දුර්වලම පේළි” යන ගැටලුවේදී අපට ලබා දී ඇත්තේ අ අනුකෘතියයි පේළි 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) මොකද අපි ලකුණු ගබඩා කරනවා. මෙහි n යනු අනුකෘතියේ පේළි ගණන වේ.

ආශ්රිත