K ყველაზე სუსტი მწკრივები მატრიცის Leetcode გადაწყვეტაში  


Რთული ტური Easy
ხშირად ეკითხებიან Amazon
ალგორითმები Array ორობითი ძებნა კოდირება ინტერვიუ ინტერვიუს მოსამზადებელი LeetCode LeetCodeSolutions

პრობლემის განცხადება  

პრობლემის ”K სუსტი რიგები მატრიქსში” მოცემულია ა matrix 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 სუსტი მწკრივების მიდგომა მატრიცის Leetcode ამოხსნაში  

მიდგომის უკეთ გასაგებად მოდით გამოვიყენოთ იგივე მაგალითი უკეთ გასაგებად. დაითვალეთ თითოების რიგი თითოეულ რიგში. მაგრამ როდესაც ამას გავაკეთებთ სრული მწკრივის გავლით, ამას წრფივი დრო დასჭირდება. დროის სირთულის გასაუმჯობესებლად ვიყენებთ ორობით ძიებას, რომ ვიპოვოთ თითოეული მწკრივის პირველი ნულის ინდექსი და ეს ინდექსი იქნება თითოეული მწკრივის ერთეულების რაოდენობა.

იხილეთ ასევე
რომაულის მთელი რიცხვი

ჩვენ გვინდა დალაგება გავაკეთოთ ორი პირობით:

  1. თითოეული მწკრივის რაოდენობა.
  2. თუ ერთეულის რაოდენობა ტოლია, მაშინ მწკრივის ნომერი.

ამ ხრიკის გამოყენებით შეგვიძლია მისი ერთ ცვლადად გადაკეთება. ჩვენ შეგვიძლია შევქმნათ ქულა აღწერიდან დალაგების პირობების შესატყვისი.

მატრიქსში ყველაზე სუსტი მწკრივების Leetcode ამოხსნაPin

 

ანგარიში = ჯარისკაცები დათვლა * რიგები + მიმდინარე RowIndex

ასე რომ, ჩვენ შეგვიძლია მივიღოთ ჯარისკაცების დათვლა ქულის / რიგების მიხედვით და rowIndex ქულების% რიგების მიხედვით

ახლა ჩვენ დავალაგებთ ქულას და საწყისი კ ქულის ინდექსი იქნება პასუხი.

განხორციელება

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 სუსტი მწკრივების Java- ის კოდი მატრიქსში

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 სუსტი მწკრივების სირთულის ანალიზი მატრიცული Leetcode ხსნარში  

დროის სირთულე

ზემოთ მოცემული კოდის სირთულეა O (n * logm + nlogn). n * logm არის თითოეული რიგის ერთეულების გამოსათვლელად და n * logn არის დახარისხებისთვის. აქ n არის მწკრივების რიცხვი და m არის სვეტების რაოდენობა.

იხილეთ ასევე
სტუდენტთა დასწრების ჩანაწერი I Leetcode Solution

კოსმოსური სირთულის

ზემოთ მოცემული კოდის სივრცის სირთულეა O (n) რადგან ჩვენ ვინახავთ ქულას. აქ n არის მატრიცის მწკრივების რაოდენობა.

ლიტერატურა